P-pełne problemy na drzewach

To pytanie jest związane z jednym z moich wcześniejszych pytań, trudnymi NP na drzewach .

Szukam problemów, które są kompletne P na drzewach.

Najnowszym, zaprezentowanym na ICALP jest

Markus Lohrey, Christian Mathissen: Izomorfizm zwykłych drzew i słów. ICALP (2) 2011: 210–221

Artykuł znajdziesz zarówno na arxivie, jak i tutaj .

Innym przykładem jest epimorfizm Mostowskiego (patrz P-kompletność i efektywna równoległość Satoru Miyano oraz artykuł Dahlhaus ):

Dahlhaus E, Czy SETL jest odpowiednim językiem do programowania równoległego - podejście teoretyczne, Logika informatyki, 1st Workshop, CSL '87, Karlsruhe / FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instancja: ukierunkowany wykres acykliczny spełniający aksjomat ekstensywności i dwa wierzchołki x 1 , x 2 ∈ $D = (V, A)$$x_1, x_2 \in V$

Problem: zdecydować, czy , w którym M D jest epimorfizmem Mostowski do D .$M_D(x_1) = M_D(x_2)$$M_D$$D$

Zależy to trochę od rodzaju problemów, na które patrzysz, ale problem z systemami ścieżek może być kandydatem.

Biorąc pod uwagę: skończony zbiór zdań , zestaw ⊆ P aksjomatów, zestaw R ⊆ P × P × P reguł wnioskowania i jakiś cel p ∈ P .$P$$A \subseteq P$$R \subseteq P \times P \times P$$p \in P$

Pytanie: Czy można udowodnić, że jest w A przy użyciu R ?$p$$A$$R$

Tutaj każda propozycja w jest możliwa do udowodnienia z A za pomocą R, a jeśli istnieje reguła ( p 1 , p 2 , p 3 ) w R i p 1 i p 2 są możliwe do udowodnienia z A za pomocą R , to również p 3 można udowodnić z pomocą R .$A$$A$$R$$(p_1,p_2,p_3)$$R$$p_1$$p_2$$A$$R$$p_3$$A$$R$

Chodzi o to, że strukturą takiego dowodu jest drzewo.

Blisko spokrewnionym problemem jest problem pustki języka dla gramatyki bezkontekstowej: czy mając gramatykę bezkontekstową, ma ona co najmniej jedno drzewo derywacji? (Redukcja z systemów ścieżek jest niemal natychmiastowa.) Dlatego pustka językowa gramatyk bezkontekstowych jest P-pełna. Z bardzo podobnego powodu problem pustki dla automatów drzewnych jest również P-zupełny.

Odniesieniem do systemów ścieżek jest: Stephen Cook: Obserwacja kompromisu w zakresie przechowywania czasoprzestrzennego. JCSS, 1974.

Chciałbym zasugerować kilku możliwych kandydatów na P-kompletność:

• uogólniona gra w kamyki dla drzew (patrz „Zastosowanie uogólnionego kamykowania drzewa do rzadkiej faktoryzacji macierzy” JWH Liu)
• Problem Supertree zgodności w filogenetyce (patrz „Algorytmy o stałych parametrach dla supertrees zgodności” autorstwa D. Fernandeza-Baca i in.).

P-kompletność nie jest dla mnie jednak jasna, redukcja z HornSAT wydaje się możliwa, ale trudna; może problem wyboru zestawu docelowego byłby bardziej naturalnym punktem wyjścia?

Oto trzeci problem, o którym wspomniałem, zwany Quad Tree Recoloring. Dostajemy:

• $\Gamma = (\gamma_{i,j})$
• $T$$\Gamma$

$T$$T$$\Gamma$

Inną możliwą funkcją kosztów byłoby policzenie powierzchni przekolorowanych węzłów zamiast ich liczby. Przypuszczam, że ten problem jest P-zupełny, ale nawet członkostwo w P nie jest natychmiastowe.