<p>Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show <span class="math-container">$P/poly$</span> is not strong enough, Mulmuley's and Smale's approach (while not enough to show <span class="math-container">$P\neq NP$</span>) also tries to prove something non-trivial at the level of circuits, Jukna's remark 1.18 here <a href="http://www.thi.informatik.uni-frankfurt.de/%7Ejukna/ftp/graph-compl.pdf" rel="nofollow noreferrer">http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf</a> tries to attempt <span class="math-container">$P/poly$</span> is not strong enough etc.</p>
<blockquote>
<ol>
<li><p>Is there any known strategy to prove <span class="math-container">$P$</span> is not <span class="math-container">$NP$</span> that does not prove the stronger statement such as <span class="math-container">$NP\not\subseteq P/poly$</span>?</p>
</li>
<li><p>Assume <span class="math-container">$NP\subset P/poly$</span> holds, assume <span class="math-container">$coNP=NP=RP\neq P$</span> holds and assume <span class="math-container">$VP=VNP$</span> holds and in this scenario is there any hope to prove <span class="math-container">$P\neq NP$</span>?</p>
</li>
</ol>
</blockquote>
<p>Why negative vote (this is a perfectly reasonable query seeking whether there is any strategy known that can avoid 'circuit'ous route and also addresses one 'minuscule' probability cause of why known approaches fail (just because except <span class="math-container">$P\neq NP$</span> everything we assume is false - this probability is technically nothing yet there))?</p>

CC BY-SA 3.0
2017-08-27T20:48:37.597Z
To whoever voted to close based on unclarity. Isn't it clear what I am asking? Why go through the harder path of $P/poly$ not being powerful enough it suffices to show $P$ is not powerful enough.
Turbo
CC BY-SA 3.0
2017-08-27T20:49:55.007Z
and why negative vote (this is a perfectly reasonable query seeking whether there is any strategy known that can avoid 'circuit'ous route)?
Turbo
CC BY-SA 3.0
2017-08-27T22:51:55.317Z
The second question is unclear: what do you mean by "is there any hope"? These statements are not known to contradict P$\neq$NP, so does that qualify as "hope"?
Sasho Nikolov
CC BY-SA 3.0
2017-08-27T22:55:07.033Z
The first one is problematic too, but less so. What qualifies as a strategy? I have talked to a researcher who seriously suggested proving P$\neq$NP by proving that EXP $\subseteq$ P/poly. This is quite the opposite of showing NP$\not \subseteq$P/poly. Does it qualify?
Sasho Nikolov
CC BY-SA 3.0
2017-08-28T00:33:11.757Z
It is easy to ask difficult general, methodological, or philosophical questions (what we refer to as soft-questions), specially in complexity theory. The bar for quality of such questions is higher. They should be precise as much as possible, the author should have done their own research and demonstrate it. Anyone who is mildly familiar with complexity theory research can post hundreds of questions like this. You should explain why the answer really matters to you to show the question is not out of idle curiosity. See also https://stackoverflow.blog/2010/09/29/good-subjective-bad-subjective/
Kaveh
CC BY-SA 3.0
2017-08-28T01:11:06.703Z
Re this question, first list actively pursued approaches to separating P from NP. If you don't know any then your question is not good. Now among them is there any that you consider might satisfy your criteria? If not, then again your question is not good. Try to be more explicit about the kind of answer you really expect to get and state that more clearly.
Kaveh
CC BY-SA 3.0
2017-08-28T08:54:12.300Z
@SashoNikolov $EXP\subseteq P/poly$ indeed qualifies but I would prefer avoid circuits altogether from the picture and one which is currently considered as possible without going through circuits (the reason I mentioned all these outlier complexity class equality plausibility (such as $NP=coNP$) is to make a definitive point to seek 'if there is a strategy that is feasible without invoking circuits but one that respects current philosophy such as $NP\neq coNP$, $VP\neq VNP$, $EXP\not\subseteq P/poly$ etc'  - by asking just what strategy do we have on our plate if everything we think is false).
Turbo
CC BY-SA 3.0
2017-08-28T16:54:21.247Z
These strike me as two really separate questions: one is about whether we have any techniques for proving uniform lower bounds that don't prove the (typically stronger) nonuniform lower bound; see https://cstheory.stackexchange.com/questions/80/which-results-in-complexity-theory-make-essential-use-of-uniformity/98#98. ...
Joshua Grochow
CC BY-SA 3.0
2017-08-28T16:56:22.370Z
...the other is whether any of our current techniques could plausibly separate P from NP even if many other things we believe are false, e.g. if NP=coNP, etc. Of course one can say "Well, technique X could show P neq NP but encounter some obstacle when you try to apply X to show NP neq coNP." But we have no idea...
Joshua Grochow
<cc.complexity-theory><reference-request><turing-machines><big-picture><p-vs-np>
Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?
Turbo
# Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

(Asked by: username_0 on 2017-08-27)

Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) also tries to prove something non-trivial at the level of circuits, Jukna's remark 1.18 here [http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf](http://www.thi.informatik.uni-frankfurt.de/%7Ejukna/ftp/graph-compl.pdf) tries to attempt $P/poly$ is not strong enough etc.

> 1. Is there any known strategy to prove $P$ is not $NP$ that does not prove the stronger statement such as $NP\not\subseteq P/poly$?
> 2. Assume $NP\subset P/poly$ holds, assume $coNP=NP=RP\neq P$ holds and assume $VP=VNP$ holds and in this scenario is there any hope to prove $P\neq NP$?

Why negative vote (this is a perfectly reasonable query seeking whether there is any strategy known that can avoid 'circuit'ous route and also addresses one 'minuscule' probability cause of why known approaches fail (just because except $P\neq NP$ everything we assume is false - this probability is technically nothing yet there))?

**Tags:** cc.complexity-theory, reference-request, turing-machines, big-picture, p-vs-np

> **Comments:**
> **username_0**: To whoever voted to close based on unclarity. Isn't it clear what I am asking? Why go through the harder path of $P/poly$ not being powerful enough it suffices to show $P$ is not powerful enough.  
> **username_0**: and why negative vote (this is a perfectly reasonable query seeking whether there is any strategy known that can avoid 'circuit'ous route)?  
> **username_1**: The second question is unclear: what do you mean by "is there any hope"? These statements are not known to contradict P$\neq$NP, so does that qualify as "hope"?  
> **username_1**: The first one is problematic too, but less so. What qualifies as a strategy? I have talked to a researcher who seriously suggested proving P$\neq$NP by proving that EXP $\subseteq$ P/poly. This is quite the opposite of showing NP$\not \subseteq$P/poly. Does it qualify?  
> **username_2**: It is easy to ask difficult general, methodological, or philosophical questions (what we refer to as soft-questions), specially in complexity theory. The bar for quality of such questions is higher. They should be precise as much as possible, the author should have done their own research and demonstrate it. Anyone who is mildly familiar with complexity theory research can post hundreds of questions like this. You should explain why the answer really matters to you to show the question is not out of idle curiosity. See also https://stackoverflow.blog/2010/09/29/good-subjective-bad-subjective/  
> **username_2**: Re this question, first list actively pursued approaches to separating P from NP. If you don't know any then your question is not good. Now among them is there any that you consider might satisfy your criteria? If not, then again your question is not good. Try to be more explicit about the kind of answer you really expect to get and state that more clearly.  
> **username_0**: @SashoNikolov $EXP\subseteq P/poly$ indeed qualifies but I would prefer avoid circuits altogether from the picture and one which is currently considered as possible without going through circuits (the reason I mentioned all these outlier complexity class equality plausibility (such as $NP=coNP$) is to make a definitive point to seek 'if there is a strategy that is feasible without invoking circuits but one that respects current philosophy such as $NP\neq coNP$, $VP\neq VNP$, $EXP\not\subseteq P/poly$ etc'  - by asking just what strategy do we have on our plate if everything we think is false).  
> **username_3**: These strike me as two really separate questions: one is about whether we have any techniques for proving uniform lower bounds that don't prove the (typically stronger) nonuniform lower bound; see https://cstheory.stackexchange.com/questions/80/which-results-in-complexity-theory-make-essential-use-of-uniformity/98#98. ...  
> **username_3**: ...the other is whether any of our current techniques could plausibly separate P from NP even if many other things we believe are false, e.g. if NP=coNP, etc. Of course one can say "Well, technique X could show P neq NP but encounter some obstacle when you try to apply X to show NP neq coNP." But we have no idea...  

---

## 0 answers

