Problema que está em P somente se P! = NP

Existem problemas solucionáveis no tempo polinomial apenas se P! = NP e solucionáveis no tempo (digamos) ? $O(2^n)$

Um exemplo simples seria: Se P! = NP, calcule um teste de primalidade para um número aleatório de n bits, caso contrário, avalie uma posição aleatória de pior caso no xadrez generalizado de um tabuleiro nxn com 2n peças de cada lado. Isso parece meio hacky embora. Existem outros exemplos naturais?

cc.complexity-theory reference-request Phylliida
fonte

Não é exatamente o que você está perguntando, mas existem conexões entre os limites inferiores do circuito (por exemplo, o SAT requer circuitos de tamanho super polinomial, implicando particularmente que P! = NP) e a des aleatorização (por exemplo, BPP = P, em particular alguns novos problemas seriam conhecido por estar em P). Mas tenho certeza de que P! = NP não é uma suposição suficientemente forte para esse resultado.

usul

é comprovável no ZFC (problema em aberto), um algoritmo pode ser: na entrada

, se

não codificar uma prova válida de

, a saída

simula a máquina de Turing

em fita vazia para

etapas e saída

se rejeitar ou não parar,

caso contrário.

P \neq N P

$P\neq NP$

x

$x$

x

$x$

P \neq N P

$P\neq NP$

0

$0$

x

$x$

2^{| x |}

$2^{|x|}$

0

$0$

1

$1$

Marzio De Biasi

Que tal se for comprovável no HoTT, mas não no ZFC?

Chad Brewbaker

@MarzioDeBiasi Isso é verdade, obrigado, e realmente, como Chad apontou, você pode usar qualquer conjunto de axiomas no lugar do ZFC, usando um consistente que possa provar de maneira significativa que P! = NP. Isso ainda parece bastante hacky, quero dizer, como meu exemplo, poderíamos substituir facilmente os

com qualquer outra complexidade de tempo desejada (incluindo, por exemplo, a solução do problema de parada).

2^{[} | x |]

$2^[|x|]$

Phylliida

É possível que não haja exemplos de aparência natural do tipo que estou solicitando, mas parece que as definições formais de "natural" (por exemplo, alta probabilidade de escolher esse problema, devido a um problema aleatório em todos os problemas no EXP) podem ser perdidas. alguns dos significados, por isso pode não ser tão significativo tentar provar isso, não tenho certeza.

Phylliida 9/09/14

Problema que está em P somente se P! = NP

Respostas: