HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#54287, answer score: 2

Revisions (0)

No revisions yet.