In dem Film Inception Cobb wird Ariadne gebeten, ein Labyrinth zu entwerfen, dessen Gestaltung doppelt so lange dauert. Dies bietet sich für ein allgemeines Problem an, bei dem wir eine Situation haben, in der die Ressourcen um einen gewissen Betrag begrenzt sind und jeder, der überprüft, ob dieses Problem in der angegebenen Komplexitätsklasse liegt, dessen Lösung entweder mehr Zeit und / oder Platz in Anspruch nimmt. Ist das ein neues Problem?
Antworten:
Diese Situation tritt häufig in Krypto auf, wo Sie schwierige Probleminstanzen zusammen mit ihren Lösungen generieren möchten. Zum Beispiel gibt es die Arbeit von Eric Bach (und später von Adam Kalai) zur effizienten Erzeugung zufälliger Ganzzahlen mit ihren Primfaktoren.
Eine von vielen interessanten Beobachtungen von Impagliazzo und Wigderson (Zufälligkeit gegen Zeit: Derandomisierung unter einer einheitlichen Annahme. J. Comput. Syst. Sci., 63: 672–688, 2001) ist, dass man effizient zusammengesetzte Zufallsmatrizen modulo p zusammen mit erzeugen kann ihre bleibenden Karten. (Denken Sie darüber nach ... verwenden Sie die Selbstreduzierbarkeit von permanent ...) Darüber hinaus wissen wir, dass die permanente Person selbstreduzierbar ist. Dies ist also ein Beispiel für ein sehr schwieriges Problem, für das wir effizient gelöste Instanzen generieren können.
quelle
Erstens glaube ich nicht, dass das Arthur-Merlin-Protokoll in das Modell aufgenommen werden muss - es klingt aus der Motivation heraus, dass Sie nur schnell Probleminstanzen erstellen möchten, sodass jeder Algorithmus zu deren Lösung langsam ist. Mit anderen Worten, wenn wir beweisen könnten, dass Arthur ein schweres Problem produzieren kann, dann scheint es für Merlin nicht notwendig zu sein, zu überprüfen, ob das erzeugte Problem schwer ist.
Sehr verwandt ist diese Frage : Können wir in der Polynomzeit eine Sprache erzeugen, die in der Polynomzeit nicht entscheidbar ist? Die Antwort lautet ja, wenn unary P nicht gleich unary NP ist.
quelle