List of theorems stating that P does not equal NP if and only if

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.

• That would be a constant fraction of all complexity papers! – MCH Jan 19 '12 at 19:17
• 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
• @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
• @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 0:32
• @Janoma: "If X then P=NP" is the same as "If P≠NP then not-X". – Jeffε Jan 20 '12 at 2:39

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$

• May be this is straightforward: $P \ne NP$ if and only if $FP \ne FNP$. – Mohammad Al-Turkistany Jan 21 '15 at 15:55

$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.

• a ref would be good – vzn Mar 7 '14 at 16:03
• Are you sure? I hadn't heard of worst-case OWFs before, but from the notes here it looks like their existence is equivalent to $BPP \neq NP$. – Huck Bennett Mar 7 '14 at 16:09
• Yes I am sure. :) See the reference. – Mohammad Al-Turkistany Mar 7 '14 at 17:47

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

• ... on ordered structures. Otherwise we know unconditionally that such properties exist. – Emil Jeřábek Jan 21 '15 at 15:59
• @EmilJeřábek yes, on ordered structures as it was implicitly assumed by Immerman in above paper. – Mohammad Al-Turkistany Jan 21 '15 at 16:10

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
{"ft_lang_label":"__label__en","ft_lang_prob":0.87285924,"math_prob":0.9303853,"size":3625,"snap":"2019-43-2019-47","text_gpt3_token_len":999,"char_repetition_ratio":0.13835958,"word_repetition_ratio":0.1712,"special_character_ratio":0.2747586,"punctuation_ratio":0.110958904,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9975386,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-23T05:31:31Z\",\"WARC-Record-ID\":\"<urn:uuid:d327e4df-6b9b-4aaf-8f92-973abe000042>\",\"Content-Length\":\"169316\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:be0dd634-0321-45be-868e-dbb4b46c0da7>\",\"WARC-Concurrent-To\":\"<urn:uuid:a9e05ba1-0d71-4998-8432-6353f477ed54>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/9806/list-of-theorems-stating-that-p-does-not-equal-np-if-and-only-if?noredirect=1\",\"WARC-Payload-Digest\":\"sha1:DZ5QY7VWTCV6ZQRDQIULCNATGDH3HJNR\",\"WARC-Block-Digest\":\"sha1:PZRHWSQR5DT2MKHX7V5A2S2W7JJQUUMH\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987829458.93_warc_CC-MAIN-20191023043257-20191023070757-00289.warc.gz\"}"}