Palavra de aviso
Na teoria de complexidade computacional, uma palavra de aviso é uma entrada adicional para uma Máquina de Turing que é permitida depender do comprimento de entrada n, mas não sobre a própria entrada. Um problema de decisão está na classe de complexidade P/f(n) se houver uma Máquina de Turing de tempo polinomial M com a seguinte propriedade: para qualquer n, há uma palavra de aviso A de comprimento f(n), de tal modo que, para qualquer entrada x de comprimento n , a máquina M decidi corretamente o problema da entrada x , dado x e A.
A classe de complexidade mais comum envolvendo aviso é P/polinomial onde o comprimento do aviso f(n) pode ser qualquer polinômio em n. P/polinomial é igual ao problema de decisão de classes de tal modo que, para todo n, existe um Circuito booleano de tamanho polinomial decidindo corretamente o problema em todas as entradas de comprimento n. Uma direção da equivalência é fácil de ver. Se, para cada n, existe um circuito booleano de tamanho polinomial A(n) decidindo o problema, podemos usar uma Máquina de Turing que interpreta a palavra de aviso como uma descrição do circuito. Então, dada a descrição de A(n) como o aviso, a máquina vai decidir corretamente o problema em todas as entradas de comprimento n. A outra direção utiliza uma simulação de uma máquina de Turing de tempo polinomial por um circuito de tamanho polinomial como em uma prova do Teorema de Cook-Levin. Simulando uma máquina de Turing com avisos não é mais complicado do que simulando uma máquina normal, uma vez que a palavra de aviso pode ser incorporada no circuito.[1]
Devido a esta equivalência, P/polinomial às vezes é definida como a classe de problemas de decisão que podem ser resolvidos por circuitos booleanos de tamanho polinomiais, ou por um circuito booleano de tamanho polinomial não uniforme.
P/polinomial contém P e BPP (teorema de Adleman). Ele também contém alguns problemas indecidíveis, tais como a versão unary de cada problema indecidível, incluindo o Problema da parada. Por causa disso, não está contido no DTIME (f(n)) ou NTIME (f(n)) para qualquer f.
Classes de aviso podem ser definidas para outros limites de recursos ao invés de P. Por exemplo, tomando uma máquina de Turing não-determinística de tempo polinomial com um aviso de comprimento f(n) dá a classe de complexidade NP/f(n). Se nos é permitido um aviso de comprimento 2n, podemos usá-lo para codificar se cada entrada de comprimento n está contido na linguagem. Portanto, qualquer função booleana é computável com um aviso de comprimento 2n e aviso de tamanho maior que exponencial não é significativo
Similarmente, a classe L/polinomial pode ser definida como LSPACE com um aviso de valor polinomial.
Resultados conhecidos incluem::
- As classes NL/polinomial e UL/polinomial são as mesmas, exemplo, computação de espaço logarítimico não deterministico com aviso pode ser feita sem ambiguidades.[2] Esse meio pode ser provado usando o lemma de isolamento.[3]
- Sabe-se que coNEXP está contido em NEXP/poly.[4]
Referências
- ↑ Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, ISBN 9780521424264, Cambridge University Press, p. 113, Zbl 1193.68112.
- ↑ Reinhardt, Klaus; Allender, Eric (2000). «Making nondeterminism unambiguous». SIAM J. Comput. 29 (4): 1118-1131. Zbl 0947.68063. doi:10.1137/S0097539798339041
- ↑ Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002). The complexity theory companion. Col: Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-67419-5. Zbl 0993.68042
- ↑ Lance Fortnow, A Little Theorem