I'm trying to prove that P$^{NP}_{||} =$ P$^{NP}_{O(\log n)}$ where $n$ is the length of the input.

So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as logarithmically many adaptive ones.

I know I need to see both inclusions, and have worked out the "easy" one: P$^{NP}_{||} \supseteq$ P$^{NP}_{O(\log n)}$ by arranging all the logarithmically many possibilities in a long deterministic one, and then use the fact that it's still polynomial (from known time complexity properties).

Now, I bang my head on a wall when I try to do the other one. I'm not even sure of where to start. I would very much appreciate your input on this problem, and besides the problem advice on where I could read examples on similar problems to get a better hang on them.

  • 1
    $\begingroup$ (I was puzzled by that too when it came up in an answer I was reading.) ​ ​ ​ Hint: ​ What if you knew how many of the parallel queries would output YES? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Mar 11 '16 at 11:25
  • $\begingroup$ hm, that sounds like a good starting point! How could I argue that they are logarithmically many instead of polynomially? $\endgroup$ – Sara Mar 11 '16 at 11:45
  • $\begingroup$ You can't. ​ ​ ​ ​ $\endgroup$ – user12859 Mar 11 '16 at 11:48
  • 1
    $\begingroup$ Another hint: your proof will need to use the fact that the exponent is NP, not some other complexity class. Suppose you had had polynomially many instances of some NP problem, and you wanted to know whether the answer to all of them is YES (i.e., you want to know the logical and of the answers to those instances). How many queries to an NP oracle would be needed? $\endgroup$ – D.W. Mar 11 '16 at 12:04
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 12 '16 at 7:31

Please refer the theorem 7, in On Truth-Table Reducibility to SAT and the Difference Hierarchy over NP and On Truth-Table Reducibility to SAT by Samuel R. Buss. The problem you mentioned is the original result by Buss. Hemachandra proved one of the inclusions in his PhD thesis.

  • $\begingroup$ Can you provide an overview or describe the main ideas in your answer? $\endgroup$ – Ariel Mar 11 '16 at 14:14
  • $\begingroup$ @Ariel Do you want me to prove it? I will do so if you are not able to follow the proof in the reference. Hemachandra's inclusion is the difficult one, where as Buss is the easier one. $\endgroup$ – Shreesh Mar 11 '16 at 14:58

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.