Complétude et langages contextuels.

16

Je m'intéresse à deux questions concernant les langages contextuels (CSL) et l'exhaustivité:

  1. Existe-t-il une notion d'exhaustivité pour CSL et quelles langues sont complètes?
  2. Existe-t-il des CSL naturels qui sont NP-complets?

Pour 2., je peux certainement penser à des langages NP-complets naturels qui sont CSL (comme CSL est égal à NSPACE [ ], SAT est un CSL), mais je cherche l'inverse, c'est-à-dire un contexte- grammaire sensible décrivant un langage NP-complet.n

np-hardness fl.formal-languages space-bounded Michaël Cadilhac
la source
2
Voyons si je comprends bien (2): Serait-il suffisant d'écrire une grammaire contextuelle qui génère toutes les instances 3SAT valides sur un alphabet fixe de connecteurs et de variables SAT?
Evgenij Thorstensen
1
Eh bien, je n'aurais pas ajouté de variables SAT dans l'alphabet (un encodage binaire de leurs indices est assez bon), mais cela répondrait certainement à mon deuxième point!
Michaël Cadilhac
Au fait, avez-vous essayé?
Michaël Cadilhac
4
(1) Comme vous l'avez mentionné, il est possible d'écrire un CSG pour 3SAT, mais cela ressemble à écrire une description complète d'une machine de Turing pour le problème de débit maximal (ou n'importe quelle langue spécifique en P); Je ne m'attendrais pas à ce que cela donne un aperçu de la théorie de la complexité. (Mais bon, s'il s'avère le contraire, je serai heureux de l'entendre.) (2) Généralement, la notion de grammaires contextuelles et la notion d'exhaustivité NP ne vont pas bien ensemble parce que l'ensemble de contextuelles les langues ne sont pas fermées par des réductions de temps polynomial.
Tsuyoshi Ito
1
Merci pour ce commentaire Tsuyoshi. En effet, une grammaire pour 3SAT n'est probablement pas ce que je recherche, mais j'y suis allé avec la même réaction que la vôtre: si c'est un peu facile / naturel, ça m'intéresserait. Pour votre (2), l'un de mes objectifs est le suivant: disons que j'ai une classe de langages CS fermée par logspace-reduction, et je veux montrer que ma classe ne contient pas (ou est peu susceptible) de contenir des problèmes NP-complets, Je n'aurais qu'à montrer que le langage CS spécifique NP-complet n'est pas dans ma classe, ce qui pourrait être plus facile si le langage est naturellement CS.
Michaël Cadilhac

Réponses:

9

Pour répondre à votre première question, une réductibilité adaptée à vos besoins est log-lin-reducibility, qui est la réductibilité de l'espace de journalisation avec la contrainte supplémentaire que la taille de la chaîne de sortie de la réduction est au plus linéaire dans la taille de l'entrée. Si je me souviens bien, le problème d'appartenance aux grammaires contextuelles (ou, si vous le souhaitez, aux automates à liaison linéaire) est le problème canonique CSL complet par rapport à la réductibilité log-lin.

Du côté appliqué, le problème d'universalité des expressions régulières (ordinaires) sur l'alphabet binaire, est la réductibilité log-lin par CSL-complete. La notion et le résultat d'exhaustivité se retrouvent dans Albert R. Meyer et Larry J. Stockmeyer (SWAT 1972) également: Stockmeyer (thèse de doctorat, MIT 1974). Pour plus d'informations sur le contexte et des résultats similaires dans ce domaine, voir également la récente enquête de Holzer et Kutrib (DLT 2010).

EDIT (2017/03/06): Concernant votre deuxième question, la réponse acceptée à la question ci-dessous cite un article de Rounds (1973), qui construit un automate de pile imbriqué à sens unique reconnaissant SAT. Bien que SAT ne soit pas considéré comme un CSL "naturel", il peut être utile de rechercher dans la littérature d'autres exemples d'automates de pile imbriqués unidirectionnels ou de grammaires indexées.

Grammaire contextuelle pour SAT?

Hermann Gruber
la source
Merci beaucoup, c'est bien ce que je cherchais!
Michaël Cadilhac
Pour l'édition: Fantastique! Merci d'être revenu et d'avoir rempli cette réponse, c'est un grand esprit!
Michaël Cadilhac