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.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.