Ich habe ein Entscheidungsproblem mit $ 2 ^ N $ Bit-Zertifikaten, wie würde ich mein Entscheidungsproblem effizient überprüfen, wenn es in $ NP $ ist?

Question

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 $ 2 ^ K $ + $ M $ . ( Verwenden Sie AKS, um die Konditionen zu entscheiden )

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 2 ^ N $ Größe sein kann, wie würde ich das Entscheidungsproblem bei der Polynomzeit überprüfen, wenn man bedenkt, dass ich nur ansehen kann? Übergangstaaten als Zertifikat an sich?

Mit anderen Worten, wie würde ein Polynom-Zeit-Verifizierer für dieses Entscheidungs-Problem aussehen?

Answer 1

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.