Was ist der axiomatische Kontext (Mengenlehre) der Vermutungen P vs NP und NP = EXPTIME?

Wenn die Vermutung oder gesetzt ist (z. B. vom Clay Mathematical Institute von S. Cook, siehe hier ), welches mathematische axiomatische System wird angenommen? $\mathbf{P} = \mathbf{NP}$ $\mathbf{P} \neq \mathbf{NP}$

Um solche Aussagen zu beweisen oder zu widerlegen, müssen Sie einige Axiome annehmen. Welche? Nur die Peano-Arithmetik (2. Sprache)? Die Zermelo-Fraenkel-Mengenlehre mit dem Axiom der Wahl? Kleinere axiomatische Mengen-Theorien (zB Gödels konstruierbare Mengen, wo auch die Kontinuumshypothese gilt, siehe hier )?

Offensichtlich sollte es eine axiomatische Theorie sein, die das zählbare Unendliche akzeptiert. Aber welche im Besonderen? Gibt es ein veröffentlichtes Ergebnis, das sie in einer bestimmten axiomatischen Mengenlehre als konsistent erweisen würde? (Mit anderen Worten, Definieren eines Modells, in dem es wahr ist, aber nicht behauptet, in allen Modellen wahr zu sein).

cc.complexity-theory model-theory Konstantin Kyritsis
quelle

Es basiert im Allgemeinen auf dem TM-Modell, von dem bisher keine besondere Abhängigkeit von der Wahl der Axiome der Mengenlehre nachgewiesen wurde ... bis jetzt!

vzn

D T I M E (n^{α (n)})

$\mathsf{DTIME}(n^{\alpha(n)})$

α (n)

$\alpha(n)$

siehe auch Ergebnisse in TCS unabhängig von ZFC, was ungefähr "nicht viel bisher"

anzeigt

Π_{1}^{0}

$\Pi^0_1$

P \neq N P

$P\neq NP$

S A T

$SAT$

Π_{1}^{0}

$\Pi^0_1$ im Allgemeinen .

Damiano Mazza

@ DamianoMazza Danke Damiano, Sie haben Recht, entschuldigen Sie, dass Sie einen unglaublich starken Anspruch erhoben haben.

Sasho Nikolov

Antworten:

Es ist nicht angegeben. Wenn es genügend Kandidatenpapiere gibt, die vorgeben, P ≟ NP zu lösen, wird ein Sonderbeirat gebildet, der entscheidet, ob (und an wen) der Preis vergeben wird. Ich gehe davon aus, dass der Sonderbeirat entscheiden wird, ob Ihr Axiomensystem akzeptabel ist. Wenn Sie ZF mit Wahl annehmen, garantiere ich Ihnen, dass sie es nehmen werden. Wenn Sie P ≠ NP als Axiom annehmen, garantiere ich Ihnen, dass dies nicht der Fall ist.

Peter Shor
quelle

Es wäre ziemlich interessant / bizarr, wenn für den Beweis eine Auswahl erforderlich wäre (dh ZFC funktioniert, ZF nicht).

Usul

Ich danke den Leuten für ihre bisherigen Antworten. Es ist sinnvoll, dass es nicht spezifiziert ist und es variabel ist, welches axiomatische (Mengenlehre) System angenommen wird. Es scheint mir, dass es in einer ziemlich restriktiven axiomatischen Mengenlehre (oder einem restriktiven Modell der axiomatischen Mengenlehre) wahrscheinlicher ist, dass man NP = EXPTIME und in einem pluralistischeren (axiomatisches System oder Modell der Mengenlehre) wahrscheinlicher beweisen kann NP ist nicht EXPTIM (feinere Grade von Komplexitätsunterschieden).

Constantine Kyritsis

Und selbst es kann vorkommen, dass man mit einem Beweis kommen kann, dass innerhalb der Peano-Arithmetik (mit Mengen, die nur ohne Axiome der Mengenlehre aus logischen Formeln definiert werden können) die berühmten Vermutungen unabhängig und nicht beweisbar sind (es sei denn, es gibt bereits ein Ergebnis über diese Vermutungen im Inneren Peano-Arithmetik oder ein einfacheres Unmöglichkeitsargument, das ich nicht kenne).

Constantine Kyritsis

Niemand glaubt ernsthaft, dass P! = NP unabhängig von ZFC ist. Wir kennen keine nicht erfundenen mathematischen Aussagen, die von ZFC unabhängig sind (außer den offensichtlichen Godelschen). Dieses Ergebnis wird einfach nicht passieren.

David Harris

@usul: Es ist nicht nur bizarr, es ist in der Tat unmöglich. Bei arithmetischen Aussagen ist ZFC gegenüber ZF konservativ.

Emil Jeřábek