Hierarquia polinomial
Na teoria da complexidade , a hierarquia polinomial é uma hierarquia de classes de complexidade que estende a noção de classes P , NP , co-NP . A classe PH é a união de todas as classes da hierarquia polinomial.
Definições
Existem várias definições equivalentes das classes da hierarquia polinomial.
Como uma alternância de quantificadores
A hierarquia pode ser definida usando os quantificadores universal ( ) e existencial ( ). Em primeiro lugar, para qualquer polinômio e qualquer linguagem , definimos
∀{\ displaystyle \ forall}
∃{\ displaystyle \ existe}
p{\ displaystyle p}
eu{\ displaystyle L}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
∃peu: ={x∈{0,1}∗ | (∃C∈{0,1}≤p(|x|))⟨x,C⟩∈eu}{\ displaystyle \ existe ^ {p} L: = \ left \ {x \ in \ {0,1 \} ^ {*} \ \ left | \ \ left (\ existe w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ right \}}![\ existe ^ p L: = \ left \ {x \ in \ {0,1 \} ^ * \ \ left | \ \ left (\ exists w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ direito \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/512f95a25246a8b68415f5390a4728e5aba00c90)
,
ou seja, o conjunto contém exatamente o conjunto de palavras para as quais existe uma palavra de tamanho polinomial no comprimento de x tal que a palavra está inserida . Intuitivamente, a palavra desempenha o papel de um certificado para um certificado relativamente pequeno em comparação com . Da mesma forma, definimos
∃peu{\ displaystyle \ existe ^ {p} L}
x{\ displaystyle x}
C{\ displaystyle w}
⟨x,C⟩{\ displaystyle \ langle x, w \ rangle}
eu{\ displaystyle L}
C{\ displaystyle w}
x{\ displaystyle x}
x{\ displaystyle x}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
∀peu: ={x∈{0,1}∗ | (∀C∈{0,1}≤p(|x|))⟨x,C⟩∈eu}{\ displaystyle \ forall ^ {p} L: = \ left \ {x \ in \ {0,1 \} ^ {*} \ \ left | \ \ left (\ forall w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ right \}}![\ forall ^ p L: = \ left \ {x \ in \ {0,1 \} ^ * \ \ left | \ \ left (\ forall w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ direito \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68acf3bac948fb1f98a71f0346db809cadbe1878)
.
Estendemos essas definições para classes de linguagem VS{\ displaystyle {\ mathcal {C}}}
∃PVS: ={∃peu | p é um polinômio e eu∈VS}{\ displaystyle \ exists ^ {\ rm {P}} {\ mathcal {C}}: = \ left \ {\ exists ^ {p} L \ | \ p {\ mbox {é um polinômio e}} L \ in {\ mathcal {C}} \ right \}}
∀PVS: ={∀peu | p é um polinômio e eu∈VS}{\ displaystyle \ forall ^ {\ rm {P}} {\ mathcal {C}}: = \ left \ {\ forall ^ {p} L \ | \ p {\ mbox {é um polinômio e}} L \ in {\ mathcal {C}} \ right \}}
Agora, podemos definir as classes da hierarquia polinomial por indução da seguinte forma:
Σ0P: =Π0P: =P{\ displaystyle \ Sigma _ {0} ^ {\ rm {P}}: = \ Pi _ {0} ^ {\ rm {P}}: = {\ rm {P}}}
Σk+1P: =∃PΠkP{\ displaystyle \ Sigma _ {k + 1} ^ {\ rm {P}}: = \ existe ^ {\ rm {P}} \ Pi _ {k} ^ {\ rm {P}}}
Πk+1P: =∀PΣkP{\ displaystyle \ Pi _ {k + 1} ^ {\ rm {P}}: = \ forall ^ {\ rm {P}} \ Sigma _ {k} ^ {\ rm {P}}}
PH=⋃k∈NÃOΣkP{\ displaystyle {\ rm {PH}} = {\ underset {k \ in \ mathbb {N}} {\ bigcup}} \ Sigma _ {k} ^ {\ rm {P}}}
Em particular, e .
NÃOP=Σ1P{\ displaystyle {\ rm {NP}} = \ Sigma _ {1} ^ {\ rm {P}}}
vsoNÃOP=Π1P{\ displaystyle {\ rm {coNP}} = \ Pi _ {1} ^ {\ rm {P}}}![{\ rm coNP} = \ Pi_1 ^ {\ rm P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2541f15490c7874d129c93694d8d2d4cca43996f)
Com máquinas oracle
A hierarquia polinomial também pode ser definida usando a máquina de Turing com oráculo . denota a classe de problemas que podem ser resolvidos por máquinas de complexidade aumentada por um oráculo de complexidade .
NOB{\ displaystyle A ^ {B}}
NO{\ displaystyle A}
B{\ displaystyle B}![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
Nós posamos
Δ0P=Σ0P=Π0P=P{\ displaystyle \ Delta _ {0} ^ {P} = \ Sigma _ {0} ^ {P} = \ Pi _ {0} ^ {P} = {\ mbox {P}}}![{\ displaystyle \ Delta _ {0} ^ {P} = \ Sigma _ {0} ^ {P} = \ Pi _ {0} ^ {P} = {\ mbox {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18995b1ff1976989dc9ddc477a7196b27635cced)
Então, para todo i ≥ 0:
Δeu+1P: =PΣeuP{\ displaystyle \ Delta _ {i + 1} ^ {P}: = {\ mbox {P}} ^ {\ Sigma _ {i} ^ {P}}}
Σeu+1P: =NPΣeuP{\ displaystyle \ Sigma _ {i + 1} ^ {P}: = {\ mbox {NP}} ^ {\ Sigma _ {i} ^ {P}}}
Πeu+1P: =co-NPΣeuP{\ displaystyle \ Pi _ {i + 1} ^ {P}: = {\ mbox {co-NP}} ^ {\ Sigma _ {i} ^ {P}}}
Com máquinas alternadas
A hierarquia polinomial pode ser definida usando máquinas de Turing alternadas . é a classe de linguagens decidida por uma máquina de Turing alternada em tempo polinomial, em que qualquer execução é composta por i sequências de configurações do mesmo tipo (existenciais ou universais), a primeira sequência contendo apenas configurações existenciais. A definição de é semelhante, mas as configurações do primeiro conjunto são universais.
ΣeuP{\ displaystyle \ Sigma _ {i} ^ {P}}
ΠeuP{\ displaystyle \ Pi _ {i} ^ {P}}![{\ displaystyle \ Pi _ {i} ^ {P}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa92b55f7a4de22aa5229de7253661d14e5ba7c7)
Exemplos de problemas
Se uma fórmula de lógica proposicional é mínima, isto é, se não há fórmulas equivalentes mais curtas, é um problema algorítmico em .
Σ2P{\ displaystyle \ Sigma _ {2} ^ {P}}![{\ displaystyle \ Sigma _ {2} ^ {P}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e45acb23af4adb55ad3e2c030392ab86740e9009)
Propriedades
Pergunta sobre o colapso
Outra propriedade importante, interna à hierarquia polinomial, é :, o que significa que se em um nível duas classes são iguais, então todas as classes “acima” são iguais. Em seguida, falamos de "colapso da hierarquia polinomial no nível ".
∀eu,ΣeuP=ΠeuP⇒ΣeuP=PH{\ displaystyle \ forall i, \ Sigma _ {i} ^ {P} = \ Pi _ {i} ^ {P} \ Rightarrow \ Sigma _ {i} ^ {P} = PH}
eu{\ displaystyle i}
eu{\ displaystyle i}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
Temos a inclusão: PH PSPACE . A igualdade entre PH e PSPACE não é conhecida. Mas a igualdade implicaria que a hierarquia polinomial entre em colapso.
⊆{\ displaystyle \ scriptstyle \ subseteq}
Em particular, se , então , isto é : a hierarquia polinomial colapsa no nível 1. Portanto, não pensamos que a hierarquia polinomial colapsa no nível 1 (esta é a questão P = NP ).
P=NÃOP{\ displaystyle P = NP}
NÃOP=vsoNÃOP{\ displaystyle NP = coNP}
Σ1P=Π1P{\ displaystyle \ Sigma _ {1} ^ {P} = \ Pi _ {1} ^ {P}}![\ Sigma _ {1} ^ {P} = \ Pi _ {1} ^ {P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba65f2d4379dd3123b886038fc00ebf91a56abf4)
Aulas probabilísticas
E foi o elo com a classe probabilística BPP : é o teorema Sipser-Gács-Lautemann . As relações entre PH e a classe de complexidade quântica BQP também foram estudadas.
BPP⊆Σp2∩Πp2{\ displaystyle BPP \ subseteq \ Sigma _ {p} ^ {2} \ cap \ Pi _ {p} ^ {2}}![BPP \ subseteq \ Sigma _ {p} ^ {2} \ cap \ Pi _ {p} ^ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ee7c28a5e6215a397a2b9dce2454ffbdcd4c19a)
Bibliografia
-
AR Meyer e LJ Stockmeyer . O problema de equivalência para expressões regulares com quadratura requer espaço exponencial. Em Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , pp. 125–129, 1972. O artigo que introduziu a hierarquia.
-
LJ Stockmeyer . A hierarquia de tempo polinomial . Ciência da Computação Teórica , vol.3, pp. 1-22, 1976.
-
(pt) Christos Papadimitriou , Computational Complexity , Addison-Wesley ,1993( ISBN 978-0-201-53082-7 )Indivíduo. 17. Hierarquia polinomial , pp. 409–438.
-
(pt) Michael R. Garey e David S. Johnson , Computers and Intratability: A Guide to the Theory of NP-Completeness , New York, WH Freeman,1979, 338 p. ( ISBN 0-7167-1045-5 ) , “Seção 7.2: The Polynomial Hierarchy” , p. 161-167.
- (pt) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 5 ("A hierarquia polinomial e alternância")
Link externo
Veja também
Referências
-
(in) Sipser, Introdução à Teoria da Computação
-
(em) Scott Aaronson , "BQP and the polynomial hierarchy" in STOC ,
2010, p. 141-150.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">