Suppose that someone found an algorithm A for a NP problem (that is not NP-compl

Question

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

Explanation / Answer

I think I see where your confusion arises. Hopefully ;).

Suppose you have a problem ??NP, and two algorithms A and B that both solve ?.

Assume that A uses algorithm A? as a sub-algorithm, where A? is acutally an algorithm for a PSPACE-complete problem.

Also assume that B is the same as A, but instead of using A? as a sub-algorithm, it uses B?, which is sufficient to solve ?, 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)?f(x)+h(x) and g(x)?f(x)+q(x). Sort of. But not really.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.