P-lengkapi masalah pada pohon

Pertanyaan ini terkait dengan salah satu pertanyaan saya sebelumnya, masalah NP-hard pada pohon .

Saya mencari masalah yang P-lengkap di pohon.

Yang terbaru, disajikan di ICALP adalah

Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221

Anda akan menemukan kertas di arxiv dan di sini .

Contoh lain adalah epimorfisme Mostowski (lihat kelengkapan-P dan paralelisasi efisien oleh Satoru Miyano, dan makalah oleh Dahlhaus ):

Dahlhaus E, Apakah SETL bahasa yang cocok untuk pemrograman paralel - pendekatan teoretis, logika ilmu Komputer, Lokakarya 1, CSL '87, Karlsruhe / FRG 1987, Lect. Catatan Komputasi. Sci. 329, 56-63, 1988)

Contoh: grafik asiklik langsung memuaskan aksioma ekstensionalitas dan dua simpul x 1 , x 2 ∈ $D = (V, A)$$x_1, x_2 \in V$

Soal: Tentukan apakah , di mana M D adalah epimorphism Mostowski untuk D .$M_D(x_1) = M_D(x_2)$$M_D$$D$

Tergantung sedikit pada masalah apa yang Anda lihat, tetapi masalah sistem jalur mungkin menjadi kandidat.

Mengingat: Sebuah himpunan berhingga dari proposisi , satu set A ⊆ P aksioma, satu set R ⊆ P × P × P aturan inferensi dan beberapa sasaran p ∈ P .$P$$A \subseteq P$$R \subseteq P \times P \times P$$p \in P$

Pertanyaan: Apakah dapat dibuktikan dari A menggunakan R ?$p$$A$$R$

Di sini, setiap proposisi dalam dapat dibuktikan dari A menggunakan R dan, jika ada aturan ( p 1 , p 2 , p 3 ) dalam R dan p 1 dan p 2 dapat dibuktikan dari A menggunakan R , maka juga p 3 dapat dibuktikan dari Sebuah menggunakan R .$A$$A$$R$$(p_1,p_2,p_3)$$R$$p_1$$p_2$$A$$R$$p_3$$A$$R$

Intinya adalah bahwa struktur bukti semacam itu adalah pohon.

Masalah yang berkaitan erat adalah masalah kekosongan bahasa untuk tata bahasa bebas konteks: Diberi tata bahasa bebas konteks, apakah ia memiliki setidaknya satu pohon derivasi? (Pengurangan dari sistem jalur hampir segera.) Oleh karena itu, kekosongan bahasa tata bahasa bebas konteks adalah P-lengkap. Karena alasan yang sangat mirip, masalah kekosongan untuk tree automata juga P-complete.

Referensi pada sistem jalur adalah: Stephen Cook: Pengamatan tentang penyimpanan ruang-waktu trade-off. JCSS, 1974.

Saya ingin menyarankan beberapa kandidat yang mungkin untuk P-kelengkapan:

• Game Pebbling Umum untuk pohon (lihat "Aplikasi Pebbling Pohon Umum untuk Faktorisasi Matriks Jarang" oleh JWH Liu)
• Perjanjian Supertree masalah dalam filogenetik (lihat "Algoritma Parameter Tetap untuk Perjanjian Supertrees" oleh D. Fernandez-Baca et al).

Kelengkapan P tidak jelas bagi saya, pengurangan dari HornSAT tampaknya mungkin tetapi rumit; mungkin masalah Pemilihan Set Target akan menjadi titik awal yang lebih alami?

Ini adalah masalah ketiga yang saya sebutkan, yang disebut Quad Tree Recoloring. Kita diberi:

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

$T$$T$$\Gamma$

Fungsi biaya lain yang mungkin adalah menghitung permukaan node yang di-recolored alih-alih jumlahnya. Saya menduga bahwa masalah ini P-lengkap, tetapi bahkan keanggotaan dalam P tidak langsung.