0
$\begingroup$

Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$ ?

I found a proof with padding arguments (wikipedia), that $$ P = NP \Rightarrow EXP = NEXP $$ If an oracle $A$ exists with $P=NP$ and $EXP\not=NEXP$ relative to $A$ then the padding technique would be a proof methode, that circumvents the Relativization Barrier.

Maybe padding arguments can help to solve problems like P vs. NP.

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes, there is an oracle with $P^A = NP^A$ and $EXP^A \not= NEXP^A$.

It is an exercise in Odifreddi: Classical Recursion Theory Vol. II on page 253. An example is in Kurtz : Sparce sets in NP - P: relativization S.I.A.M J. Comp. 14(1985) 113-119

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.