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 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))?

  • 3
    $\begingroup$ 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"? $\endgroup$ – Sasho Nikolov Aug 27 '17 at 22:51
  • 2
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Aug 27 '17 at 22:55
  • 4
    $\begingroup$ 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 stackoverflow.blog/2010/09/29/good-subjective-bad-subjective $\endgroup$ – Kaveh Aug 28 '17 at 0:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 28 '17 at 1:11
  • 2
    $\begingroup$ 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 cstheory.stackexchange.com/questions/80/…. ... $\endgroup$ – Joshua Grochow Aug 28 '17 at 16:54

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.