Problème qui est dans P seulement si P! = NP

Y a-t-il des problèmes qui ne peuvent être résolus en temps polynomial que si P! = NP, et autrement résolu en (disons) temps? $O(2^n)$

Un exemple simple serait: si P! = NP, calculez un test de primalité pour un nombre aléatoire de n bits, sinon, évaluez une position aléatoire dans le pire des cas aux échecs généralisés d'une carte nxn avec 2n pièces de chaque côté. Cela semble un peu hacky cependant. Y a-t-il des exemples plus naturels?

cc.complexity-theory reference-request Phylliida
la source

Pas exactement ce que vous demandez, mais il existe des connexions entre les bornes inférieures du circuit (par exemple, SAT nécessite des circuits de taille super-polynomiale, impliquant notamment que P! = NP) et la dérandomisation (par exemple BPP = P, en particulier, de nouveaux problèmes pourraient être connu pour être en P). Mais je suis à peu près sûr que P! = NP n'est pas une hypothèse assez forte pour un tel résultat.

usul

est prouvable dans ZFC (problème ouvert) alors un algorithme pourrait être: sur l'entrée

, si

ne code pas une preuve valide de

alors la sortie

sinon simule la machine de Turing

sur une bande vide pour

étapes et sortie

si elle rejette ou ne s'arrête pas,

sinon.

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

Et si c'était prouvable dans HoTT mais pas dans ZFC?

Chad Brewbaker

@MarzioDeBiasi C'est vrai, merci, et vraiment, comme Chad l'a souligné, vous pouvez utiliser n'importe quel ensemble d'axiomes à la place de ZFC, en utilisant, espérons-le, un axiome cohérent qui peut prouver de manière significative que P! = NP. Cela semble encore assez hacky, je veux dire, comme mon exemple, nous pourrions facilement remplacer le

avec toute autre complexité temporelle souhaitée (y compris, par exemple, la résolution du problème d'arrêt).

2^{[} | x |]

$2^[|x|]$

Phylliida

Il est possible qu'il n'y ait pas d'exemples d'apparence naturelle du type que je demande, mais cela semble être des définitions formelles de "naturel" (disons, une forte probabilité de choisir ce problème étant donné un problème aléatoire dans tous les problèmes d'EXP) une partie du sens, donc ce n'est peut-être pas si significatif d'essayer de le prouver, je ne suis pas sûr.

Phylliida

Problème qui est dans P seulement si P! = NP

Réponses: