# See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$

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.

• (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? ​ ​ ​ ​ ​ ​ ​ ​ – user12859 Mar 11 '16 at 11:25
• hm, that sounds like a good starting point! How could I argue that they are logarithmically many instead of polynomially? – Sara Mar 11 '16 at 11:45
• You can't. ​ ​ ​ ​ – user12859 Mar 11 '16 at 11:48
• 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? – D.W. Mar 11 '16 at 12:04
• 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! – Raphael Mar 12 '16 at 7:31