Ich habe ein Entscheidungsproblem mit $ 2 ^ N $ Bit-Zertifikaten, wie würde ich mein Entscheidungsproblem effizient überprüfen, wenn es in $ NP $ ist?
-
29-09-2020 - |
Frage
Entscheidungsproblem: ist $ 2 ^ K $ + $ M $ A Prime?
Die Eingänge für beide $ K $ und $ M $ sind nur ganze Zahlen. Die Lösung ist die Summe der
Die Befugnisse von 2 haben ungefähr $ 2 ^ N $ Ziffern. Betrachten Sie $ 2 ^ K $ wo $ k $ = 100000. Vergleichen Sie die Anzahl der Ziffern in $ K $ in die Anzahl der Ziffern in seiner Lösung!
Frage
sehen, dass das Zertifikat des Entscheidungsproblems
Mit anderen Worten, wie würde ein Polynom-Zeit-Verifizierer für dieses Entscheidungs-Problem aussehen?
Lösung
Ein Entscheidungsproblem hat eine Ja / Nein-Antwort, sodass es keine "exponentielle Größe" hat.Sie fragen nach Suchproblemen, diese können sicherlich exponentielle Größe haben.Und ja, wenn die Größe der Lösung (in einem bestimmten kompakten Format abgeschrieben ist), das ist), ist es in der Größe des ursprünglichen Problems exponentiell, es ist eindeutig nicht möglich, die Antwort in der Polynomzeit sogar aufzuschreiben.
In jedem Fall gelten P und NP strikt nur für Entscheidungsprobleme.Schauen Sie sich jedoch einen Blick auf Belare's "Entscheidung gegen Sucht" für aBeziehung zwischen beiden.