Concept

P/poly

En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP. Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens, l'autre avec des machines de Turing. Une famille de circuits est une suite infinie , , ..., , ... où est un circuit booléen bits d'entrée. Lorsque est une chaîne de bits de longueur , on notera le résultat de l'évaluation du circuit lorsque le ème bit d'entrée de est affecté à la valeur du ème bit de , pour tout . La classe P/poly est la classe des langages tels qu'il existe une famille de circuits et un polynôme tels que : la taille de est au plus ; pour tout , si et seulement si est vrai, où est la taille de . On dit d'un langage satisfaisant cette propriété qu'il a des circuits polynomiaux. On peut définir P/poly de manière équivalente en utilisant des machines de Turing déterministes qui prennent conseil. Une telle machine, a le droit d'utiliser un mot fini cn, qui sert de conseil pour traiter toutes les instances x de taille n. Un problème est dans P/poly s'il existe une machine de Turing M en temps polynomial et une suite de mots finis c0, c1, c2,... où cn est de taille polynomiale en n, tels que pour tout mot x de longueur n, x est une instance positive ssi M(x, cn) = 1. Les mots finis c0, c1, c2,... s'appellent des conseils. La classe P est incluse dans la classe P/poly (P peut être définie comme P/poly sauf avec des familles de circuits uniformes en temps polynomial). P/poly contient des problèmes décidables et hors de P. Remarquons qu'il n'est pas nécessaire que le circuit correspondant à une entrée de taille puisse être construit en temps polynomial, ni même de façon déterministe.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (1)
PHYS-641: Quantum Computing
After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament
Séances de cours associées (18)
Éléments de complexité computationnelle
Introduit la complexité computationnelle, les problèmes de décision, la complexité quantique et les algorithmes probabilistes, y compris les problèmes dures au NP et les problèmes complets au NP.
Éléments de complexité informatique
Couvre les concepts et les implications de complexité informatique classique et quantique.
Éléments de complexité computationnelle
Couvre les algorithmes quantiques, les classes de complexité, l'algorithme de Grover et l'information quantique dans la complexité computationnelle.
Afficher plus
Publications associées (7)

On the complexity of linearizability

Jad Hamza

It was previously shown that the problem of verifying whether a finite concurrent system is linearizable can be done with an EXPSPACE complexity. However, the best known lower bound is PSPACE-hardness, and can be obtained using a reduction from control-sta ...
SPRINGER WIEN2019

Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments

Anastasios Kyrillidis

The maximization of a positive (semi) definite complex quadratic form over a finite alphabet is NP-hard and achieved through exhaustive search when the form has full rank. However, if the form is rank-deficient, the optimal solution can be computed with on ...
IEEE2011

Strategy logic

We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alt ...
2010
Afficher plus
Concepts associés (12)
Hiérarchie polynomiale
En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Liste de classes de complexité
This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics. Many of these classes have a 'co' partner which consists of the complements of all languages in the original class. For example, if a language L is in NP then the complement of L is in co-NP. (This does not mean that the complement of NP is co-NP—there are languages which are known to be in both, and other languages which are known to be in neither.
Circuit booléen
vignette|Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne. Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité.
Afficher plus