Die berühmte Isomorphismus-Vermutung von Berman und Hartmanis besagt, dass alle vollständigen Sprachen polynomiell zeitisomorph (p-isomorph) zueinander sind. Die Schlüsselbedeutung der Vermutung ist, dass sie impliziert . Es wurde 1977 veröffentlicht und ein Beleg dafür war, dass alle zu diesem Zeitpunkt bekannten vollständigen Probleme tatsächlich p-isomorph waren. Tatsächlich waren sie alle auffüllbar , was eine schöne natürliche Eigenschaft ist und auf nichttriviale Weise einen p-Isomorphismus impliziert.
Seitdem hat sich das Vertrauen in die Vermutung verschlechtert, da vollständige Kandidatensprachen entdeckt wurden, die wahrscheinlich nicht p-isomorph zu , obwohl das Problem immer noch offen ist. Nach meinem Kenntnisstand stellt jedoch keiner dieser Kandidaten ein natürliches Problem dar; Sie werden durch Diagonalisierung konstruiert, um die Isomorphismus-Vermutung zu widerlegen.
Trifft es nach fast vier Jahrzehnten immer noch zu, dass alle bekannten natürlichen vollständigen Probleme p-isomorph zu ? Oder gibt es einen mutmaßlichen natürlichen Kandidaten für das Gegenteil?
quelle
Antworten:
Ich denke, die Antwort lautet ja, auch heute noch ist kein natürliches Problem bekannt, das als Kandidat für die Verletzung der Isomorphismus-Vermutung in Frage kommt.
Der Hauptgrund ist, dass normalerweise natürliche NP-vollständige Probleme sehr leicht als paddingfähig angesehen werden können, was Berman und Hartmanis als ausreichend für SAT-isomorph erwiesen haben. Bei Problemen mit natürlichen Graphen werden normalerweise zusätzliche Scheitelpunkte hinzugefügt, die z. B. nicht mit dem Graphen verbunden oder auf eine ganz bestimmte (aber normalerweise offensichtliche) Weise verbunden sind. Bei der Entscheidungsversion von Optimierungsproblemen werden normalerweise neue Dummy-Variablen ohne Einschränkungen hinzugefügt. Und so weiter.
quelle