Using the cut property that states that for any cut the edge with the smallest weight is contained in a MST. So, could cut the graph up into pieces and run a O(n) (where n is edges) algorithm on each of the pieces. Just need to show that merging is correct.
Category: CS Theory
Proof that the counting subset sum is in #P (Sharp P)
Yesterday I gave a presentation proving that in theory group. Presenting a proof is a lot harder than it seems when proving it to yourself on paper. Suggestion for presentations in the future: say what I am going to do then write it up on the board. Then after writing point to the different equations… Continue reading Proof that the counting subset sum is in #P (Sharp P)
Visualizing Complexity Results
https://app.box.com/s/pd6jz1124xsx5kgvz5i4 I found this image here. I thought it did a good job of visualizing the complexity space. It seems like they have some interesting posts as well.
What is #P (Sharp P)
#P is the set of counting problems whose corresponding decision problem is in NP. Or more formally (from here): A function [math]f:left{0,1right}^*rightarrow mathbb{N}[/math] is in #[math]bf{P}[/math] if there exists a polynomial [math]p: mathbb{N}rightarrow mathbb{N}[/math] and a polynomial-time TM (turing machine) M such that for every [math]xin left{0,1right}^*[/math] [math]f(x)=left|{left{yin left{0,1right}^{p^{(|x|)}}:M(x,y)=1right}}right|[/math]. I later intend to find a proof or develop… Continue reading What is #P (Sharp P)