patternMinor
See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$
Viewed 0 times
thatseelog
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#54287, answer score: 2
Revisions (0)
No revisions yet.