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.



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.

Browse other questions tagged or ask your own question.