1
$\begingroup$

We think that non-deterministic machines are more powerful than deterministic machines, by giving an oracle access to $P\subseteq L\subseteq NP$, it seems reasonable to expect there's some $L$ that is so weak compared to $SAT$ and thus gives "relatively more" power to $P$ than to $NP$.

Suppose we're given a monotonically harder sequence of oracle access, $$ L_0 (\in P)\leq_P L_1 \leq_P L_2\leq_P\dots\leq_P L_k= SAT, $$ We'll have $$ P=P^{L_0}\subseteq P^{L_1}\subseteq ... \subseteq P^{L_k}=NP\\ NP=NP^{L_0}\subseteq NP^{L_1}\subseteq ... \subseteq NP^{L_k}=\Sigma_2P $$

Suppose we can find, in the middle $L_i$ that does not give extra power to $NP$, i.e. $NP^{L_i}\subseteq NP$, but $L_i$ is already hard enough so that, in such relativised world we could resolve $P^{L_i}\neq NP^{L_i}$, then we'll have $P\subseteq P^{L_i}\subsetneq NP^{L_i}=NP$. So my question is,

Do we have any barrier result against this type of technique when resolving $P$ vs $NP$ ? It seems neither a relativizing technique nor a natural proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.