Problem Detail: In http://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?
Asked By : Albert Hendriks
Answered By : Alex Meiburg
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45635
