3

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

Community
  • 1
Turbo
  • 12,812
  • 1
  • 19
  • 68
  • 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 Aug 27 '17 at 20:48
  • and why negative vote (this is a perfectly reasonable query seeking whether there is any strategy known that can avoid 'circuit'ous route)? – Turbo Aug 27 '17 at 20:49
  • 3
    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 Aug 27 '17 at 22:51
  • 2
    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 Aug 27 '17 at 22:55
  • 4
    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 Aug 28 '17 at 00:33
  • 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. – Kaveh Aug 28 '17 at 01:11
  • @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 Aug 28 '17 at 08:54
  • 2
    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 Aug 28 '17 at 16:54
  • 1
    ...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 Aug 28 '17 at 16:56

0 Answers0