Nachfolgend meine Vereinfachung eines Teils eines größeren Forschungsprojekts zu räumlichen Bayes'schen Netzwerken:
Angenommen, eine Variable ist " -local" in einer Zeichenfolge wenn zwischen dem ersten und dem letzten Satz, in dem sie vorkommt, weniger als Klauseln stehen (wobei eine natürliche Zahl ist).
Betrachten Sie nun die Teilmenge die durch das Kriterium definiert ist, dass für jedes jede Variable in ist lokal. Für welches (falls vorhanden) ist NP-hart?
Folgendes habe ich bisher in Betracht gezogen:
(1) Variationen der Methode zum Zeigen, dass in P ist, indem jede Disjunktion als Implikation und gerichtete Pfade auf dem gerichteten Graphen dieser Implikationen untersucht werden ( hier angegeben und ausführlich auf S. 184 dargestellt) 185 von Papadimitrious Computerkomplexität ). Anders als in gibt es eine Verzweigung der gerichteten Pfade in , aber möglicherweise ist die Anzahl der gerichteten Pfade durch die räumlichen Einschränkungen der Variablen begrenzt. Bisher kein Erfolg damit.
(2) Eine Polynomzeitreduktion von (oder einem anderen bekannten NP-vollständigen Problem) auf . Zum Beispiel habe ich verschiedene Schemata zur Einführung neuer Variablen ausprobiert. Um die Klauseln zusammenzuführen, die die ursprüngliche Variable enthalten , muss ich jedoch im Allgemeinen "Ketten" zusätzlicher Klauseln ziehen, die die neuen Variablen enthalten, und diese beeinträchtigen die räumlichen Einschränkungen für die anderen Variablen.
Sicher bin ich hier nicht auf Neuland. Gibt es ein bekanntes NP-hartes Problem, das auf reduziert werden kann, oder verhindern die räumlichen Einschränkungen, dass das Problem so schwierig ist?
quelle