NEXPTIME
Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado.
Em termos de NTIME, temos que
Um importante conjunto de problemas NEXPTIME-completos estão relacionados à circuitos sucintos. Circuitos sucintos são simplesmente máquinas que descrevem grafos em espaço exponencialmente menor. Estes aceitam dois números de vértices como entrada e saída se existe uma ligação entre eles. Se solucionar um problema em um grafo em uma representação natural, tal como matrix de adjacencia, é NP-completo, então solucionar o mesmo problema em uma reapresentação de circuitos sucinto é NEXPTIME-completo, porque a entrada é exponencialmente menor.[1] Ou seja, encontrar um caminho hamiltoniano para um grafo codificado de tal forma é NEXPTIME-completo.
Se P = NP, então NEXPTIME = EXPTIME; mais precisamente, E ≠ NE se e somente se existe uma linguagem em NP que não está em P.[2]
Caracterização alternativa[editar | editar código-fonte]
NEXPTIME comumente aparece no contexto de sistemas interativos de provas, onde existe duas maiores caracterizações para eles. A primeira é de sistema de prova MIP, onde temos dois grandes poderosos provadores que se comunicam com um verificador polinomial randomico (mais não cada um entre si). Se uma cadeia encontra-se na linguagem, então deve-se o verificador deve estar convencido disto com grande probabilidade. Se a cadeia não está na linguagem, então não deve ser possível enganar o verificador a aceitar tal cadeia exceto com uma probabilidade baixa. O fato do sistema de provas MIP poder solucionar cada problema em NEXPTIME é impressionante quando consideramos que apenas um provador está presente, apenas podemos reconhecer PSPACE; a habilidade do verificador de testar com os dois provadores lhe dá grandes poderes.
Outra caracterização como sistema de prova interativo é NEXPTIME sendo uma certa classe de um prova probabilisticamente verificavel. Temos então que NP pode ser vista como classe dos problemas onde um todo poderoso provador dá uma prova uma cadeia é de uma dada linguagem, e uma máquina máquina polinomial determinística verifica se tal prova é válida. Fazemos duas mudanças para tal construção:
- Adicionar aleatoriedade, a habilidade de jogar moedas, para à máquina verificadora.
- Em vez de simplesmente dar uma suporta prova para o verificador na fita, dar uma acesso aleatório para a prova. O verificador pode especificar um índice para a cadeia da prova e receber bit correspondente. Dado que o verificador pode escrever um índice de tamanho polinomial, este pode potencialmente indexar sobre uma cadeia de prova exponencialmente longa.
Estas duas extensões juntas amplamente estendem o poder do sistema de prova, possibilitando este a reconhecer linguagens em NEXPTIME. Esta classe é chamada PCP(poly, poly). Procure por prova verificável probabilisticamente para maiores detalhes.
Referências
- ↑ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
- ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library
Bibliografia[editar | editar código-fonte]
- Michael Sipser (2006). «Sections 8.14&ndash». Introdução à Teoria da Computação. [S.l.]: THOMSON. pp. 365–367. ISBN 0-534-95097-3
