4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

I can tell that you are confused from your question, but unfortunately I am not sure what's confusing you, maybe you can add more detail.

Now to answer you question, it is inconclusive given your description. The fact that you can solve a problem from one class by solving another problem from another class does not mean that you need do so.

The way reduction usually works (assuming you want to show that problem X is "hard" in some sense) is by showing that another problem Y can be solved by solving X plus some easy extra work, where Y is known to be "hard" in some sense.

Now back to your question. Suppose that we want to sort $n$ integers (a problem in NP). We do so by first solving a PSPACE problem, throw away the result, and use quick sort. This is effectively algorithm A that you described, and you can see why this does not say anything about the complexity classes involved.

$\endgroup$
  • $\begingroup$ 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. So, math and computer science are different in this perspective, right? $\endgroup$ – Zat Mack Jul 12 '12 at 0:59
1
$\begingroup$

Luke illustrates one point of confusion; let me point out another one.

Algorithm $A$ for problem $P \in \mathsf{NP}$ uses algorithm $B$ for problem $Q \in \mathsf{PSPACE}\text{-complete}$. Is it possible that $A$ is "fast", that is it is not slower than $\mathsf{NP}$ allows for?

Yes! $Q$ may be harder than $P$, but maybe $A$ only ever calls $B$ with easy instances and thus stays within reasonable bounds! For example, $A$ may use $B$ on polynomially many instances of $Q$ of size at most $10$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.