LOGCFL - LOGCFL

Dans la théorie de la complexité computationnelle , LOGCFL est la classe de complexité qui contient tous les problèmes de décision qui peuvent être réduits dans l' espace logarithmique à un langage sans contexte . Cette classe est située entre NL et AC ¹ , en ce sens qu'elle contient la première et est contenue dans la seconde. Les problèmes qui sont complets pour LOGCFL incluent de nombreux problèmes dont les instances peuvent être caractérisées par des hypergraphes acycliques :

• évaluation de requêtes conjonctives booléennes acycliques
• vérifier l'existence d'un homomorphisme entre deux structures relationnelles acycliques
• vérifier l'existence de solutions de problèmes de satisfaction de contraintes acycliques

Voir également

• Liste des classes de complexité

Liens externes

• Complexité Zoo : LOGCFL