Diese Frage bezieht sich auf eine meiner vorherigen Fragen, NP-harte Probleme an Bäumen .
Ich suche nach Problemen, die auf Bäumen P-vollständig sind.
cc.complexity-theory
graph-theory
tree
p-hardness
Shiva Kintali
quelle
quelle
Antworten:
Eine kürzlich auf der ICALP vorgestellte ist
Markus Lohrey, Christian Mathissen: Isomorphismus regelmäßiger Bäume und Wörter. ICALP (2) 2011: 210 & ndash; 221
Sie finden das Papier sowohl auf arxiv als auch hier .
Ein weiteres Beispiel ist der Mostowski-Epimorphismus (siehe P-Vollständigkeit und effiziente Parallelisierung von Satoru Miyano und das Papier von Dahlhaus ):
Dahlhaus E, Ist SETL eine geeignete Sprache für paralleles Programmieren - ein theoretischer Ansatz, Informatiklogik, 1. Workshop, CSL '87, Karlsruhe / BRD 1987, Lect. Anmerkungen Comput. Sci. 329, 56-63, 1988)
Instanz: Ein gerichteter azyklischer Graph , der das Axiom der Extensionalität und zwei Eckpunkte x 1 , x 2 ∈ V erfülltD=(V,A) x1,x2∈V
Problem: Entscheide, ob , wobei M D der Mostowski-Epimorphismus für D ist .MD(x1)=MD(x2) MD D
quelle
Es hängt ein bisschen davon ab, welche Art von Problemen Sie untersuchen, aber das Problem mit den Pfadsystemen ist möglicherweise ein Kandidat.
Gegeben: Eine endliche Menge von Sätzen , einen Satz A ⊆ P der Axiome, einen Satz R ⊆ P × P × P von Inferenzregeln und einige Ziel p ∈ P .P A⊆P R⊆P×P×P p∈P
Frage: Ist mit R von A beweisbar ?p A R
Hier ist jeder Satz in mit R aus A beweisbar und wenn es in R eine Regel ( p 1 , p 2 , p 3 ) gibt und p 1 und p 2 mit R aus A beweisbar sind , dann ist auch p 3 aus beweisbar Eine Verwendung von R .A A R (p1,p2,p3) R p1 p2 A R p3 A R
Der Punkt ist, dass die Struktur eines solchen Beweises ein Baum ist.
Ein eng verwandtes Problem ist das Problem der Sprachlosigkeit für eine kontextfreie Grammatik: Gibt es bei einer kontextfreien Grammatik mindestens einen Ableitungsbaum? (Die Reduktion von Pfadsystemen ist fast unmittelbar.) Daher ist die sprachliche Leere von kontextfreien Grammatiken P-vollständig. Aus einem sehr ähnlichen Grund ist das Problem der Leerheit für Baumautomaten ebenfalls P-vollständig.
Eine Referenz zu Pfadsystemen ist: Stephen Cook: Eine Beobachtung zum Time-Space-Speicher-Kompromiss. JCSS, 1974.
quelle
Ich möchte einige mögliche Kandidaten für die P-Vollständigkeit vorschlagen:
Die P-Vollständigkeit ist mir jedoch nicht klar, eine Reduktion von HornSAT scheint möglich, aber schwierig; Vielleicht wäre das Problem der Zielgruppenauswahl ein natürlicherer Ausgangspunkt?
quelle
Hier ist das dritte Problem, das ich erwähnt habe: Quad Tree Recoloring. Wir erhalten:
und das Ziel ist die minimale Anzahl von Knoten umfärben , so dass keine zwei benachbarten Knoten von T werden durch Farben benachbart in beschrifteter Γ .T T Γ
Eine andere mögliche Kostenfunktion wäre, die Oberfläche der neu eingefärbten Knoten anstelle ihrer Anzahl zu zählen. Ich vermute, dass dieses Problem P-vollständig ist, aber selbst die Mitgliedschaft in P ist nicht unmittelbar.
quelle