[Solved]: Concept of reduction and algorithm

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