18

I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on and so forth.

Tayfun Pay
  • 2,598
  • 2
  • 18
  • 45
  • 15
    That would be a constant fraction of all complexity papers! – Mahdi Cheraghchi Jan 19 '12 at 19:17
  • 5
    I would say: "list of conditions implying P?NP", since not all those theorems are "if and only if". Also, I guess people are more interested --in general-- in knowing how to prove P?NP by proving something else, than in listing the many consequences of this result, a topic that has been widely discussed elsewhere. – Janoma Jan 19 '12 at 19:37
  • 2
    @Janoma: if you want to restrict yourself to implications, then the list will be really huge, given the enormous amount of results of the form: "If P!=NP, then problem X cannot be solved exactly / approximated within a constant factor in polynomial time". The question should be much more focused or better stated if we want to avoid that. – Anthony Labarre Jan 19 '12 at 22:58
  • 1
    @AnthonyLabarre: I said "list of conditions implying P?NP", not implied by P?NP. That is, a list of statements of the form "If [condition], then P=NP" or "If [condition], then P!=NP". The idea, as I hinted, is to avoid "listing the many consequences of this result" (P=NP or P!=NP). – Janoma Jan 19 '12 at 23:43
  • 4
    @Janoma: That does not solve Anthony’s well-founded concern. Hypotheses which imply P=NP are simply negations of consequences of P≠NP, and hypotheses which imply P≠NP are negations of consequences of P=NP. If SAT is solvable in polynomial time, then P=NP. If Max3SAT is polynomial-time approximable within a constant factor less than 8/7, then P=NP. And so on. – Tsuyoshi Ito Jan 20 '12 at 00:32
  • @Tsuyoshilto: true, but I guess many of the problems will fall under a same category (e.g. for any NP-complete problem X we can say "If X is solvable in polynomial time, then P=NP"). Still, given these observations, I'd say that a better question (for a wiki, perhaps), would be maintaining a list of statements directly implied by or implying one of the outcomes of P?NP, not in the philosophical, "Impagliazzo's Worlds" sense, but in a more "mathematical" (for lack of a better word) fashion (for example: "if P=NP then there are polynomial-time algorithms for problems X, Y and Z"). – Janoma Jan 20 '12 at 01:10
  • 7
    @Janoma: "If X then P=NP" is the same as "If P≠NP then not-X". – Jeffε Jan 20 '12 at 02:39
  • 2
    this doesn't seem like a real question, but a list. I think this is considered off-topic now that we can't make 'community wiki' questions. Although I think such a resource would be useful, I am not sure if cstheory is the best way to produce such a resource. – Artem Kaznatcheev Jan 20 '12 at 17:05
  • a well known open, apparently stronger conjecture than $\mathsf{P} \neq \mathsf{NP}$ is that there are no polynomial-sized circuits over the complete basis (AND,OR,NOT gates) to solve $\mathsf{NP}$-complete problems. but it is not known if $\mathsf{P} \neq \mathsf{NP}$ implies that such circuits dont exist. – vzn Jan 20 '12 at 15:52

4 Answers4

11

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
11

Here is a one:

Mahaney's Theorem: There is no sparse NP-complete set if and only if $P \ne NP $
(under Karp reduction).

Another one is:

$P \ne NP$ if and only if $P \ne PH$

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
8

Here is a result from descriptive complexity theory:

$P \ne NP$ if and only if some second order property is not expressible using first order logic plus least fixed point.

Reference: Immerman, Languages that capture complexity classes

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
7

Ladner theorem can be stated as:

$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.

Incomplete set is a set that is not complete for $NP$ under many-one polynomial time reductions.

Reference

Complexity Theory and Cryptology: An Introduction to Cryptocomplexity By Jörg Rothe, page 106

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149