Déclarations impliquant

22

Il s'agit en quelque sorte d'une question ouverte - pour laquelle je m'excuse à l'avance.

Y a-t-il des exemples de déclarations qui (apparemment) n'ont rien à voir avec la complexité ou les machines de Turing mais dont la réponse impliquerait ? $\mathbf{P}\neq \mathbf{NP}$

cc.complexity-theory complexity-classes p-vs-np Dominic van der Zypen
la source

4

"Il n'y a pas de système de preuve pour la logique propositionnelle dans laquelle chaque tautologie a une preuve de polynôme (dans la longueur de )." compter, ou est-ce trop proche de la complexité en raison de la limite polynomiale?

φ

$\varphi$

φ

$\varphi$

Jan Johannsen

Comme il n'y a pas de réponses "exactes" à ma question, votre conjecture compterait ... Je cherche juste des angles surprenants et différents sur le problème P vs NP

Dominic van der Zypen

4

Je suppose que la complexité descriptive donne quelques exemples. Par exemple, la déclaration «il existe des propriétés (de structures ordonnées) exprimables par des formules existentielles de second ordre qui ne peuvent pas être exprimées par des formules universelles de second ordre» est équivalente à la réponse de @ JanJohannsen, tandis que «il existe des propriétés (de structures ordonnées) exprimables par deuxième ordre formules existentielles qui ne peuvent pas être exprimées par des premières commandes formules avec un point fixe moins opérateur » est précisément

P \neq N P

$\mathsf P\neq\mathsf{NP}$ . Est-ce que cela compte?

Damiano Mazza

"

N \neq 1

$\mathbf{N}\neq 1$ et

P \neq 0

$\mathbf{P}\neq 0$ " * rimshot *

David Richerby

1

Question similaire cstheory.stackexchange.com/questions/9806/…

Tayfun Pay

14

Un système de preuve pour la logique propositionnelle est appelé polynomialement borné , si chaque tautologie $\varphi$ a une preuve dans le système de longueur polynomiale dans la longueur de $\varphi$ .

La déclaration « Il n'y a pas de système de preuve propositionnelle limitée polynomiale » est équivalent à par un résultat classique de Cook et Reckhow , il implique . $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ $\mathsf{P} \neq \mathsf{NP}$

Jan Johannsen
la source

2

Je pense que (par la définition d'un système de preuve propositionnelle pour le langage complet des tautologies

), l'hypothèse ("Il n'y a pas de système de preuve pour la logique propositionnelle dans laquelle chaque tautologie

a une preuve de polynôme (dans la longueur de

) longueur ") est presque identique à l'hypothèse que

; et donc presque identique à l' hypothèse

.

c o N P

$\mathsf{coNP}$

φ

$\varphi$

φ

$\varphi$

N P \neq c o N P

$\mathsf{NP}\neq\mathsf{coNP}$

N P \neq P

$\mathsf{NP}\neq\mathsf{P}$

Iddo Tzameret

@IddoTzameret: mais nous devons savoir que la TAUTOLOGIE est

-complète, non? Et ce n'est pas anodin. Je suppose que cet exemple ne fait que réaffirmer l'intérêt d'avoir des problèmes complets "naturels": on peut parler de classes de complexité sans parler explicitement des machines utilisées pour les définir (ce qui semble être ce que l'OP demande). Ou peut-être que j'ai mal compris votre commentaire ...

c o N P

$\mathsf{coNP}$

Damiano Mazza

@Damiano, je pense que le fait que TAUT soit coNP-complet est trivial, dans le sens où cela est impliqué par sa définition et l'exhaustivité NP de SAT.

Iddo Tzameret

@IddoTzameret, d'accord, mais vous convenez que la complétude

de SAT n'est pas anodine, non? C'est essentiellement ce que je disais. Je veux dire, entre l'énoncé "

" formulé en termes de machines de Turing et leur temps d'exécution et le stament "il n'y a pas de système de preuve propositionnelle borné polynomialement" Je vois un écart non trivial, ils ne font définitivement pas ' t regardez "presque identique". Cet écart est dans l'exhaustivité de TAUT ou SAT, selon ce que vous aimez, mais il est là. Tu n'es pas d'accord?

N P

$\mathsf{NP}$

N P \neq c o N P

$\mathsf{NP}\neq\mathsf{coNP}$

Damiano Mazza

1

Oui, la propriété "

est une preuve de

" doit être vérifiable en temps polynomial (en

et

). Et elle doit être solide et complète, c'est-à-dire qu'une formule doit avoir une preuve si elle est une tautologie.

p

$p$

φ

$\varphi$

| p |

$|p|$

| φ |

$|\varphi|$

Jan Johannsen

12

La théorie de la complexité géométrique (GCT) (également [1]) n'a pas encore été mentionnée. C'est un vaste programme ambitieux pour connecter P vs NP à la géométrie algébrique. Par exemple, un bref résumé de l'enquête Comprendre l'approche Mulmuley-Sohoni de P vs NP , Regan:

La stabilité est officieusement une notion de ne pas être «chaotique» et est devenue une branche majeure de la géométrie algébrique sous l'influence directrice de DA Mumford, entre autres. Ketan Mulmuley et Milind Sohoni [MS02] observent que de nombreuses questions sur les classes de complexité peuvent être reformulées comme des questions sur la nature des actions de groupe sur certains vecteurs dans certains espaces qui codent des problèmes dans ces classes. Cette enquête explique leur cadre d'un point de vue profane et tente d'évaluer si cette approche ajoute vraiment un nouveau pouvoir aux attaques contre la question P. vs NP.

aussi quelques synopsis dans la section "Un nouvel espoir?" dans Status of the P vs NP problem , Fortnow (2009)

Mulmuley et Sohoni ont réduit une question sur la non-existence d'algorithmes à temps polynomial pour tous les problèmes NP-complets à une question sur l'existence d'un algorithme à temps polynomial (avec certaines propriétés) pour un problème spécifique. Cela devrait nous donner de l'espoir, même face aux problèmes (1) - (3).

Néanmoins, Mulmuley pense qu'il faudra environ 100 ans pour mener à bien ce programme, s'il fonctionne.

[1] Explication de style Wikipedia de la théorie de la complexité géométrique (tcs.se)

vzn
la source

Merci d'avoir amené GCT! Il semble toucher à mon propre problème [M], mais je ne l'avais pas rencontré auparavant. "Ces problèmes de calcul peuvent être caractérisés par leurs symétries. Le programme vise à utiliser ces symétries pour prouver les limites inférieures."

DukeZhou

10

Le résultat suivant de Raz (Fonctions insaisissables et limites inférieures pour les circuits arithmétiques, STOC'08) vise (et pas directement ), mais il pourrait être suffisamment proche pour l'OP: $VP\neq VNP$ $P\neq NP$

$f:\mathbb F^n \to \mathbb F^m$ $(s, r)$ $Γ : \mathbb F^s → \mathbb F^m$ $r$ $f$ $\not⊂$ $Γ$

Pour de nombreux réglages des paramètres , les constructions explicites de mappages polynomiaux insaisissables impliquent des limites inférieures fortes (jusqu'à exponentielles) pour les circuits arithmétiques généraux. $n, m, s, r$

Iddo Tzameret
la source

Qu'est-ce qu'une cartographie polynomiale? Voulez-vous dire "polynôme"? Voulez-vous dire "fonction calculable en temps polynomial"? Autre chose?

DW

2

C'est simplement une séquence de polynômes, chacun avec les mêmes variables; il définit donc un mappage de à .

m

$m$

n

$n$

F^{n}

$\mathbb{F}^n$

F^{m}

$\mathbb{F}^m$

Iddo Tzameret

9

il existe un domaine de complexité quelque peu / récemment étudié, appelé complexité des graphes, qui étudie la façon dont les graphiques plus grands sont construits à partir de graphiques plus petits à l'aide d'opérations ET et OU des arêtes. Jukna a une belle enquête . en particulier en utilisant des unités de "graphes stellaires" il y a un théorème clé, voir p20 remarque 1.18 (le théorème est techniquement plus fort que ci-dessous et implique en fait ): $P \ne NP/poly$

Nous savons déjà (Théorème 1.7) qu'il existe des graphes bipartis G de complexité étoile ; en fait, ce sont presque tous les graphiques. D'un autre côté, le lemme de fort grossissement implique que même une borne inférieure de l' pour une constante arbitrairement petite sur la complexité des étoiles d'un graphique explicite avec aurait de grandes conséquences sur la complexité du circuit: un tel graphe donnerait une fonction booléenne explicite nécessitant un circuit exponentiel (au nombre $n × m$ $Star(G) = (nm/ \log n)$ $Star(G) ≥ (2+c)n$ $c > 0$ $n×m$ $G$ $m = o(n)$ $f_G$ $\log_2 nm$ des variables) taille! (Rappelons que, pour les fonctions booléennes, même les bornes inférieures super-linéaires ne sont pas connues jusqu'à présent.) En particulier, si le graphe est tel que la contiguïté des sommets dans peut être déterminée par une machine de Turing non déterministe fonctionnant en polynôme temporel dans la longueur binaire des codes de sommets, puis une inférieure pour une constante arbitrairement petite impliquerait que . Ainsi, la complexité en étoile des graphiques capture l'un des problèmes les plus fondamentaux de l'informatique. $G$ $G$ $log_2 n$ $Star(G) ≥ (2 + c)n$ $c > 0$ $P \ne NP$

vzn
la source

6

Je pense que vous voulez dire . L'instruction déjà trivialement connue.

P / p o l y ⊅ N P

$P/poly \not \supset NP$

P \neq N P / p o l y

$P \neq NP/poly$

Yonatan N

@YonatanN est vrai?

P \neq N P / p o l y

$P\neq NP/poly$

T ....

Oui. Même P / poly est connu pour contenir des problèmes en dehors de P, comme le problème d'arrêt unaire.

Yonatan N

Merci pour le lien Jukna! "La complexité est l'un des phénomènes scientifiques cruciaux de notre temps. Dans ce chapitre, nous considérons la complexité des graphiques."

DukeZhou

1

Que diriez-vous de Philip Maymin

"Les marchés sont efficaces si et seulement si P = NP "

RB
la source

3

Les affirmations et les "preuves" de cet article ne semblent pas rigoureuses et les arguments me semblent manquants. Avez-vous lu cet article?

Rahul Savani

J'y suis allé, et je suis d'accord que la méthodologie n'est pas si convaincante, c'est pourquoi je l'ai appelé une "revendication" plutôt qu'un résultat.

RB

5

Et il est écrit dans Microsoft Word: /

gigaoctets

0

$P$ $NP$ $FP$ $FNP$ $P$ $=$ $NP$ $P$ $NP$ $1$ $FP$ $FNP$ $FNP$ $FP$ $=$ $FNP$ $P$ $=$ $NP$

user3483902
la source

Déclarations impliquant

Réponses: