Problem Detail: Suppose that someone found an algorithm A for a NP problem (that is not NP-complete) that uses an algorithm B for PSPACE-complete or #P-complete problem during execution. (Remaining part of the algorithm takes polynomial time.) Then suppose there is also an algorithm C for a NP problem that uses the polynomial-consuming part of the algorithm A. The rest of the algorithm C is actually an algorithm that solves NP-complete problems. Then would this mean that PSPACE-complete or #P-complete collapse to NP-complete? If so or if not, why would it be like that? I am asking this question, because I seem to get confused during reading my computation textbook. Edit: I was a bit confused as in (or more accurately scalar function) math, if g(x)=f(h(x)) and g(x)=f(q(x)), h(x) and q(x) must be virtually the same. So, my question was virtually the aforementioned. That was the parallel I was making between algorithm A and C.
Asked By : Zat Mack
Answered By : Luke Mathieson
I think I see where your confusion arises. Hopefully ;). Suppose you have a problem $Pi in NP$, and two algorithms $mathcal{A}$ and $mathcal{B}$ that both solve $Pi$. Assume that $mathcal{A}$ uses algorithm $mathcal{A’}$ as a sub-algorithm, where $mathcal{A’}$ is acutally an algorithm for a $PSPACE$-complete problem. Also assume that $mathcal{B}$ is the same as $mathcal{A}$, but instead of using $mathcal{A’}$ as a sub-algorithm, it uses $mathcal{B’}$, which is sufficient to solve $Pi$, but not to solve the $PSPACE$-complete problem. I think this is the situation you want to describe? Now I think your confusion comes from assume that because a problem has two different algorithms, that the algorithms must have the same complexity – at least this is what I get from the analogy with the functions. This isn’t true, you can quite happily have an algorithm which solves a problem, but is actually far more powerful (i.e. it can solve a much bigger super-problem) and another algorithm that can only solve the smaller problem. These two algorithms don’t really say anything about one another (at least without a lot more information). To stretch the function analogy to its breaking point, the situation is more like $g(x) leq f(x)+h(x)$ and $g(x) leq f(x)+ q(x)$. Sort of. But not really.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2698 Ask a Question Download Related Notes/Documents
