3
$\begingroup$

In https://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, implying that the original problem is in NP.

Why is that allowed? Why are you allowed to continue after the oracle returns false? Doesn't this defeat the whole idea of NPC versus co-NPC? You could then simply use an oracle for a NP-complete problem to show that NPC = co-NPC?

I would think that the whole reduction is wrong and that the original problem is probably not in NP. Or aren't they implying that?

$\endgroup$
5
$\begingroup$

The answer in its current form shows only that it belongs to $\Delta_2^P$, or $P^{NP}$. This is a (not necessarily strict) subset of $\Sigma_2^P$, or $NP^{NP}$, which is what the asker had mentioned.

The answerer said that they don't know whether it's $\Delta_2$-complete, but doubt it; and it similarly seems unlikely that this in $NP$. (The next answer shows that it is $NP$-hard, so that if it is in $NP$, it is certainly $NP$-complete.)

You are correct that, if one wanted to show a problem to be in $NP$, one must not use multiple queries to an $NP$ oracle. As an example of how this might look, I could ask the problem: "Given these two instances of 3SAT, $(Problem_1,Problem_2)$, is exactly one satisfiable?" This is not going to be easily shown to be in $NP$, but it's easily shown in $P^{NP}$: I query the first problem, and then the second, and then I xor their answers together. This could be written as the problem existing in $DTIME(1)^{NP}$.

The exponent notation refers to oracles that they can query in constant time, only.

$\endgroup$
5
$\begingroup$

Well, nowhere does the answer claim the reduction "implies that the original problem is in NP". So, that explains your confusion. You read something into the answer that isn't actually there.

Also, the answer says "Cook reduction". This was a heads-up about the fact that it's not the Karp-style reduction you might be used to. You might like to learn about the difference between a Cook reduction vs a Karp reduction. Read https://en.wikipedia.org/wiki/Turing_reduction. As you suspected, a Karp reduction is part of what is used in the definition of NP-completeness, but this answer isn't trying to prove NP-completeness, so the Cook reduction is "allowed".

$\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.