Esta pregunta está relacionada con una de mis preguntas anteriores, problemas NP-hard en los árboles .
Estoy buscando problemas que sean P-completos en los árboles.
cc.complexity-theory
graph-theory
tree
p-hardness
Shiva Kintali
fuente
fuente
Respuestas:
Una reciente, presentada en ICALP es
Markus Lohrey, Christian Mathissen: isomorfismo de árboles y palabras regulares. ICALP (2) 2011: 210-221
Encontrará el documento tanto en arxiv como aquí .
Otro ejemplo es el epimorfismo de Mostowski (ver P-completitud y paralelización eficiente de Satoru Miyano, y el artículo de Dahlhaus ):
Dahlhaus E, ¿Es SETL un lenguaje adecuado para la programación paralela? Un enfoque teórico, lógica informática, primer taller, CSL '87, Karlsruhe / FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)
Instancia: un gráfico acíclico dirigido satisface el axioma de extensionalidad y dos vértices x 1 , x 2 ∈ VD=(V,A) x1,x2∈V
Problema: Decidir si , donde M D es el epimorfismo Mostowski para D .MD(x1)=MD(x2) MD D
fuente
Depende un poco del tipo de problemas que esté viendo, pero el problema de los sistemas de ruta puede ser un candidato.
Dado: Un conjunto finito de proposiciones , un conjunto A ⊆ P de axiomas, un conjunto R ⊆ P × P × P de reglas de inferencia y algunos objetivo p ∈ P .P A⊆P R⊆P×P×P p∈P
Pregunta: ¿Es comprobable desde A usando R ?p A R
Aquí, cada proposición en es demostrable desde A usando R y, si hay una regla ( p 1 , p 2 , p 3 ) en R y p 1 y p 2 son demostrables desde A usando R , entonces también p 3 es demostrable desde A usando R .A A R (p1,p2,p3) R p1 p2 A R p3 A R
El punto es que la estructura de tal prueba es un árbol.
Un problema estrechamente relacionado es el problema del vacío del lenguaje para una gramática libre de contexto: dada una gramática libre de contexto, ¿tiene al menos un árbol de derivación? (La reducción de los sistemas de ruta es casi inmediata). Por lo tanto, el vacío del lenguaje de las gramáticas libres de contexto es P-completo. Debido a una razón muy similar, el problema del vacío para los autómatas de los árboles también es P-completo.
Una referencia sobre los sistemas de ruta es: Stephen Cook: una observación sobre el intercambio de almacenamiento de espacio-tiempo. JCSS, 1974.
fuente
Me gustaría sugerir algunos posibles candidatos para completar P:
Sin embargo, la integridad de P no está clara para mí, una reducción de HornSAT parece posible pero difícil; ¿Quizás el problema de Selección de conjunto de objetivos sería un punto de partida más natural?
fuente
Aquí está el tercer problema que mencioné, llamado Quad Tree Recoloring. Se nos da:
Otra posible función de costo sería contar la superficie de los nodos recolorados en lugar de su número. Supongo que este problema es P-completo, pero incluso la membresía en P no es inmediata.
fuente