Key points are not available for this paper at this time.
Eine Klasse von lokalen Suchproblemen, PLS (polynomzeitliche lokale Suche), wie von D.S. Johnson et al. definiert (siehe J. Comput. Syst. Sci., Bd. 37, Nr. 1, S. 79-100 (1988)), wird betrachtet. PLS erfasst viel von der Struktur NP-Probleme auf der Ebene ihrer machbaren Lösungen und Nachbarschaften. Zuerst wird gezeigt, dass die CNF (konjunktive Normalform) Erfüllbarkeit PLS-vollständig ist, selbst bei gleichzeitig begrenzten Größen von Klauseln und begrenzter Anzahl von Vorkommen von Variablen. Dieses Ergebnis wird verwendet, um zu zeigen, dass das Problem des Reiseverkäufers unter der k-opt Nachbarschaft ebenfalls PLS-vollständig ist. Es wird argumentiert, dass PLS-Vollständigkeit das normale Verhalten NP-vollständiger Probleme ist.
Mark W. Krentel (Sun,) untersuchte diese Frage.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: