Problèmes P-complets sur les arbres

14

Cette question est liée à l'une de mes questions précédentes, les problèmes NP-difficiles sur les arbres .

Je recherche des problèmes P-complets sur les arbres.

Shiva Kintali
la source
6
Une certaine motivation pourrait aider.
Suresh Venkat
5
Je voudrais utiliser un tel problème pour prouver la dureté de certains problèmes sur les graphiques de largeur d'arbre borné.
Shiva Kintali

Réponses:

11

Une récente, présentée à l'ICALP, est

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

Vous trouverez l'article sur arxiv et ici .

Un autre exemple est l'épimorphisme de Mostowski (voir l'exhaustivité de P et la parallélisation efficace par Satoru Miyano et l'article de Dahlhaus ):

Dahlhaus E, est SETL un langage approprié pour la programmation parallèle - une approche théorique, la logique informatique, 1er atelier, CSL '87, Karlsruhe / FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: un graphe acyclique dirigé satisfaisant l'axiome d'extensionnalité et deux sommets x 1 , x 2V=(V,UNE)X1,X2V

Problème: Déterminer si , où M D est la epimorphisme Mostowski pour D .MD(x1)=MD(x2)MDD

Massimo Cafaro
la source
6

Cela dépend un peu du type de problèmes que vous regardez, mais le problème des systèmes de chemin peut être un candidat.

Étant donné: un ensemble fini de propositions , un ensemble A P d'axiomes, un ensemble R P × P × P de règles d'inférence et une cible p P .PAPRP×P×PpP

Question: est-il prouvable de A en utilisant R ?pUNER

Ici, chaque proposition dans est prouvable à partir de A en utilisant R et, s'il y a une règle ( p 1 , p 2 , p 3 ) dans R et p 1 et p 2 sont prouvables à partir de A en utilisant R , alors p 3 est également prouvable à partir de A l' aide de R .UNEUNER(p1,p2,p3)Rp1p2UNERp3UNER

Le fait est que la structure d'une telle preuve est un arbre.

Un problème étroitement lié est le problème de vide de langage pour une grammaire sans contexte: étant donné une grammaire sans contexte, a-t-elle au moins un arbre de dérivation? (La réduction des systèmes de chemin est presque immédiate.) Par conséquent, la vacuité du langage des grammaires hors contexte est P-complète. Pour une raison très similaire, le problème de vide pour les automates d'arbre est également P-complet.

Une référence sur les systèmes de chemin est: Stephen Cook: An Observation on Time-Space storage trade-off. JCSS, 1974.

Wim Martens
la source
1

Je voudrais suggérer quelques candidats possibles pour P-complétude:

  • le jeu de galets généralisés pour les arbres (voir "Une application du galet d'arbres généralisé à la factorisation à matrice clairsemée" par JWH Liu)
  • Le problème Accord Supertree en phylogénétique (voir "Algorithmes à paramètres fixes pour Accord Supertrees" par D. Fernandez-Baca et al).

Le P-exhaustivité n'est pas clair pour moi cependant, une réduction de HornSAT semble possible mais délicate; peut-être que le problème de sélection de l'ensemble cible serait un point de départ plus naturel?

NisaiVloot
la source
Sur une note connexe, je pense que l'exhaustivité P du deuxième problème découle de «Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs» de Chester et al. Je ne suis pas sûr du premier cependant.
NisaiVloot
Aussi, j'ai une idée pour un troisième problème impliquant des arbres BSP colorés, mais je dois trouver la définition précise. Restez à l'écoute ...
NisaiVloot
Votre mise à jour dans une réponse distincte à cette réponse doit être un commentaire ou une modification. Par conséquent, je l'ai supprimé.
Lev Reyzin
J'ai posté une réponse distincte pour qu'elle apparaisse dans le flux de questions, alors laissez-moi répéter: le premier problème `` Jeu de galets généralisé pour les arbres '' n'est probablement PAS complet car il semble résoluble dans l' espace O ( log 2 n ) , au moins dans sa définition actuelle. De plus, pour le deuxième problème, c'est une question d'interprétation, qu'il réponde ou non à la question - il s'agit techniquement d'un «profil d'arbre» ​​plutôt que d'un «arbre». PO(log2n)
Super8
1

Voici le troisième problème que j'ai mentionné, appelé Quad Tree Recoloring. On nous donne:

  • une matrice de couleurs ,Γ=(γi,j)
  • TΓ

TTΓ

Une autre fonction de coût possible serait de compter la surface des nœuds recolorés au lieu de leur nombre. Je suppose que ce problème est P-complet, mais même l'appartenance à P n'est pas immédiate.

Super8
la source
Pourquoi est-ce un "troisième problème"? Est-ce un ajout à une autre réponse?
Lev Reyzin
Et pourquoi ne pouvez-vous pas le combiner avec votre autre réponse?
Suresh Venkat
Oui, c'était un ajout à la réponse ci-dessus; étant donné la récente mise à jour, cela devrait être considéré comme un «deuxième problème» de mon côté. Ce problème n'était qu'une «estimation approximative» basée sur des considérations pratiques, je ne suis toujours pas sûr de l'appartenance à P; peut-être que le fait de considérer des topologies alternatives telles que les pavages hexagonaux pourrait changer la complexité? Je continuerai à chercher d'autres candidats et je fusionnerai les réponses éventuellement - en supposant que je puisse accéder aux anciens profils 'Super8' créés il y a 2 mois.
Super8
2
L'utilisation de plusieurs profils de cette façon crée de l'encombrement et davantage de travail pour les mods. Il s'agit d'une ressource partagée, et c'est à nous tous de garder les choses «en ordre».
Suresh Venkat