Lista de teoremas que afirmam que P não é igual a NP se e somente se

18

Eu acho que seria uma boa idéia fazer uma lista de teoremas afirmando que P não é igual a NP se, e somente se, tais e tais saídas, alguma classe de complexidade estiver contida em outra classe de complexidade e assim por diante.

cc.complexity-theory big-list p-vs-np Tayfun Pay
fonte

15

Isso seria uma fração constante de todos os documentos de complexidade!

MCH

5

Eu diria: "lista de condições implicando P? NP", pois nem todos esses teoremas são "se e somente se". Além disso, acho que as pessoas estão mais interessadas - em geral - em saber como provar o P? NP provando outra coisa, do que em listar as muitas conseqüências desse resultado, um tópico que foi amplamente discutido em outros lugares.

Janoma

2

@Janoma: se você quiser se restringir a implicações, a lista será realmente grande, dada a enorme quantidade de resultados do formulário: "Se P! = NP, o problema X não pode ser resolvido exatamente / aproximado de um fator constante em tempo polinomial ". A questão deve ser muito mais focada ou melhor, se quisermos evitar isso.

Anthony Labarre

4

@Janoma: Isso não resolve a preocupação bem fundamentada de Anthony. Hipóteses que implicam P = NP são simplesmente negações das conseqüências de P ≠ NP e hipóteses que implicam P ≠ NP são negações das conseqüências de P = NP. Se SAT é solucionável em tempo polinomial, então P = NP. Se o Max3SAT for aproximado no tempo polinomial dentro de um fator constante menor que 8/7, então P = NP. E assim por diante.

Tsuyoshi Ito

7

@Janoma: "Se X então P = NP" é o mesmo que "Se P ≠ NP então não-X".

Jeffε

11

Aqui está um:

Teorema de Mahaney: Não existe um conjunto NP completo esparso se e somente se (sob redução de Karp). $P \ne NP$

Outro é:

se e somente se $P \ne NP$ $P \ne PH$

Mohammad Al-Turkistany
fonte

Pode ser este é simples:

se e somente se

.

P \neq N P

$P \ne NP$

F P \neq F N P

$FP \ne FNP$

Mohammad Al-Turkistany

11

$P \ne NP$ se e somente se existirem funções unidirecionais de pior caso.

Referência:

Alan L. Selman. Uma pesquisa de funções unidirecionais na teoria da complexidade. Teoria dos sistemas matemáticos, 25 (3): 203–221, 1992.

Mohammad Al-Turkistany
fonte

1

um árbitro seria bom #

077 vzn

Você tem certeza? Eu não tinha ouvido falar de OWFs pior caso antes, mas a partir das notas aqui parece que a sua existência é equivalente a

.

B P P \neq N P

$BPP \neq NP$

Huck Bennett

Sim eu tenho certeza. :) Veja a referência.

Mohammad Al-Turkistany

8

Aqui está um resultado da teoria descritiva da complexidade:

se e somente se alguma propriedade de segunda ordem não for expressável usando a lógica de primeira ordem mais o ponto fixo mínimo. $P \ne NP$

Referência: Immerman, Idiomas que capturam classes de complexidade

Mohammad Al-Turkistany
fonte

... em estruturas ordenadas. Caso contrário, sabemos incondicionalmente que essas propriedades existem.

Emil Jeřábek apoia Monica

@ EmilJeřábek sim, em estruturas ordenadas, como foi implicitamente assumido por Immerman no artigo acima.

Mohammad Al-Turkistany

7

O teorema de Ladner pode ser afirmado como:

se e somente se existir um conjunto incompleto em $P \ne NP$ $NP-P$ .

Conjunto incompleto é um conjunto que não está completo para $NP$ com muitas reduções de tempo polinomiais.

Referência

Teoria da complexidade e criptologia: uma introdução à criptocomplexidade Por Jörg Rothe, página 106

Mohammad Al-Turkistany
fonte

Lista de teoremas que afirmam que P não é igual a NP se e somente se

Respostas: