Warum ist FACTOR im Co-NP?

12

Ich habe Probleme, mich mit den Problemen PRIME, COMPOSITE, FACTOR und deren Beziehung zur Komplexität auseinanderzusetzen. Ich verstehe, dass PRIME durch den AKS-Primalitätstest als wurde, und ich glaube, dass dies auch für COMPOSITE funktioniert.P

Wie für FACTOR,

FEINCTÖR={(m,r):s so dass1<s<r und s teilt m}

Nach dem, was ich gelesen habe, scheint es in . Ich sehe, dass es in da ein Zertifikat aus einem Hauptteiler von weniger als . Aber welche Art von Zertifikat kann nachweisen, dass es keinen solchen Primteiler gibt (in der Polynomzeit)?NPCÖ-NPNPmr

Fequish
quelle
1
Damit für eine Sprache der NP-Nachweis erbracht werden kann, dass die Eingabe zur Sprache gehört, muss ein Zertifikat vorhanden sein, das in polynomieller Zeit verifiziert werden kann. Dies bedeutet nicht, dass für Eingaben, die nicht zur Sprache gehören, ein Zertifikat vorhanden ist, das effizient überprüft werden kann.
Sashas

Antworten:

11

Ein Zertifikat dafür, dass kein nicht-trivialer Teiler von kleiner als r ist, ist die Faktorisierung von m . Wir können in der Polynomzeit überprüfen, ob alle Faktoren tatsächlich Primzahlen sind (da die Primalität nach dem AKS-Primalitätstest in P angegeben ist ), ob ihr Produkt m ist und ob alle mindestens r sind .mrmmr

Yuval Filmus
quelle
1
Vielen Dank. Und verstehe ich richtig, dass der AKS-Algorithmus uns sagen kann, ob eine Zahl in der Polynomzeit eine Primzahl ist oder nicht, aber wenn es keine Primzahl ist, sagt er uns die Faktoren nicht?
Fequish
1
@Fequish: Wenn es keine Primzahl ist, gibt AKS die Faktoren nicht an.
2
Es ist nicht bekannt, dass Factoring in polynomialer Zeit möglich ist. Der beste öffentlich bekannten Algorithmus hat heuristische Komplexität (hier n die Zahl selbst). eÖ((Logn)1/3(LogLogn)2/3)n
Yuval Filmus
5

Um Yuvals Antwort zu ergänzen: Der AKS-Primalitätstest wurde im Jahr 2002 entdeckt. Zuvor hatten wir keinen polynomiellen Zeitalgorithmus, um zu überprüfen, ob eine Zahl eine Primzahl ist. Pratt entdeckte jedoch 1975 das, was heute als Pratt-Urkunden bekannt ist, und bewies, dass Primes in NP ist. Wir können diese Primalitätszertifikate von Pratt für die Faktoren in unser Zertifikat aufnehmen, um zu zeigen, dass FACTOR in coNP ist, anstatt den AKS-Algorithmus zu verwenden, um zu überprüfen, ob die Faktoren direkt prim sind.

Denis Pankratov
quelle