P-problemas completos en los árboles

14

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.

Shiva Kintali
fuente
66
Alguna motivación podría ayudar.
Suresh Venkat
55
Me gustaría utilizar este problema para probar la dureza de algunos problemas en gráficos de ancho de árbol acotado.
Shiva Kintali el

Respuestas:

11

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 2VD=(V,A)x1,x2V

Problema: Decidir si , donde M D es el epimorfismo Mostowski para D .MD(x1)=MD(x2)MDD

Massimo Cafaro
fuente
6

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 .PAPRP×P×PpP

Pregunta: ¿Es comprobable desde A usando R ?pAR

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 .AAR(p1,p2,p3)Rp1p2ARp3AR

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.

Wim Martens
fuente
1

Me gustaría sugerir algunos posibles candidatos para completar P:

  • el juego de pelado generalizado para árboles (ver "Una aplicación de pelado de árboles generalizado para la factorización de matriz dispersa" por JWH Liu)
  • El problema del Acuerdo de Supertree en filogenética (ver "Algoritmos de Parámetros Fijos para Supertrees de Acuerdo" por D. Fernandez-Baca et al).

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?

NisaiVloot
fuente
En una nota relacionada, creo que la integridad de P del segundo problema se deriva de "Resolver la inconsistencia del triplete enraizado disolviendo multigrafos" de Chester et al. Sin embargo, no estoy seguro sobre el primero.
NisaiVloot
Además, tengo una idea para un tercer problema que involucra árboles BSP coloreados, pero tengo que descubrir la definición precisa.
Estén
Su actualización en una respuesta separada a esta respuesta debe ser un comentario o una edición. Por lo tanto, lo he eliminado.
Lev Reyzin
PO(log2n)
1

Aquí está el tercer problema que mencioné, llamado Quad Tree Recoloring. Se nos da:

  • Γ=(γi,j)
  • TΓ

TTΓ

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.

Súper 8
fuente
¿Por qué es este un "tercer problema"? ¿Es esto una adición a otra respuesta?
Lev Reyzin
¿Y por qué no puedes combinarlo con tu otra respuesta?
Suresh Venkat
Sí, esta fue una adición a la respuesta anterior; Dada la reciente actualización, esto debería considerarse como un "segundo problema" de mi parte. Este problema era solo una "estimación" basada en consideraciones prácticas, todavía no estoy seguro acerca de la membresía en P; ¿Quizás considerar topologías alternativas como las inclinaciones hexagonales podría cambiar la complejidad? Seguiré buscando otros candidatos y fusionaré las respuestas eventualmente, suponiendo que pueda acceder a los viejos perfiles 'Super8' creados hace 2 meses.
Super8
2
Usar múltiples perfiles de esta manera crea desorden y más trabajo para los mods. Este es un recurso compartido, y depende de todos nosotros mantener las cosas "ordenadas".
Suresh Venkat