IP (complexidade)

Na ciência da computação teórica , e em particular na teoria da complexidade , a classe IP (uma abreviatura para tempo polinomial interativo , ou seja, "interativo em tempo polinomial") é a classe de problemas de decisão que podem ser resolvidos por um sistema de prova interativo . O conceito de um sistema de prova interativo foi introduzido pela primeira vez em 1985 por Shafi Goldwasser , Silvio Micali e Charles Rackoff .

Sistema de prova interativo

Um sistema de prova interativo é composto por duas máquinas:

• o provador , denotado por P, que apresenta uma proposição de prova de que uma dada string w pertence a uma certa linguagem formal . Supõe-se que o Provador tem infinitas capacidades computacionais e espaciais ;
• o verificador , observou V , que testa se a prova apresentada é correta. O verificador é uma máquina de Turing probabilística operando em tempo polinomial que tem acesso a uma string binária aleatória cujo comprimento é polinomial em função do comprimento de w .

As duas máquinas trocam um número polinomial de mensagens, e quando a interação é completa, o verificador decide se w está no idioma ou não, com uma probabilidade de erro de no máximo 1/3 (portanto, qualquer idioma da classe BPP está em IP , já que o verificador pode simplesmente ignorar o Provador e tomar a decisão sozinho).

Definição

Um idioma está em IP se houver um verificador e um provador , como para qualquer palavra e para qualquer provador  : eu{\ displaystyle L}V{\ displaystyle V}P{\ displaystyle P}C{\ displaystyle w}Q{\ displaystyle Q}

C∈eu⇒Pr[(V,P) aceitaram C]≥2/3{\ displaystyle w \ in L \ Rightarrow \ Pr [(V, P) {\ text {aceitar}} w] \ geq 2/3} (completude) C∉eu⇒Pr[(V,Q) aceitaram C]≤1/3{\ displaystyle w \ notin L \ Rightarrow \ Pr [(V, Q) {\ text {aceitar}} w] \ leq 1/3} (correção)

O protocolo Arthur-Merlin , introduzido por László Babai , é semelhante, exceto que o número de voltas de interação é limitado por uma constante em vez de um polinômio.

Goldwasser et al. mostraram que os protocolos de tomada pública, que são os protocolos onde os números aleatórios usados ​​pelo verificador são fornecidos pelo provador ao mesmo tempo que as proposições de prova, não são mais poderosos do que os protocolos de sorteio privado rodadas adicionais de interação são necessárias para replicar o efeito de um sorteio privado e, inversamente, o verificador ainda pode enviar os resultados de seu sorteio privado para o Provador. Isso mostra que os dois tipos de protocolos são equivalentes.

Igualdade com PSPACE

A classe IP é igual a PSPACE . Este resultado é devido a Shamir, baseado no trabalho de Lund, Fortnow, Farloff, Nisan.

Este é um importante teorema da complexidade algorítmica, que demonstra que um sistema de prova interativo pode ser usado para decidir se uma string é parte de uma linguagem de tempo polinomial, mesmo que a prova tradicional em PSPACE possa ser exponencialmente longa.

Variantes

Existem várias variações de IP que alteram ligeiramente a definição do sistema de evidências interativo. Resumimos aqui os mais famosos.

mergulhar

Uma subclasse de IP é a de provas interativas determinísticas, que é semelhante ao IP, mas usa um verificador determinístico (ou seja, não aleatório). Esta classe NP .

Completude perfeita

Uma definição equivalente de IP substitui a condição de que a interação é bem-sucedida por uma alta probabilidade em strings de linguagem pela condição de que sempre é bem  - sucedida :

C∈eu⇒Pr[V↔P aceita C]=1{\ displaystyle w \ in L \ Rightarrow \ Pr [V \ leftrightarrow P {\ text {aceita}} w] = 1}

Este critério aparentemente mais forte de "completude perfeita" não altera realmente a classe IP , uma vez que qualquer idioma com um sistema de prova interativo tem um sistema de prova interativo com completude perfeita.

MIP

Em 1988, Goldwasser et al. criaram um sistema de prova interativa baseado em IP ainda mais poderoso chamado MIP , para o qual existem dois provadores independentes. Os dois provadores não podem se comunicar depois que o verificador começa a enviar mensagens para eles. Assim como é mais fácil saber se um criminoso está mentindo se ele e seu parceiro forem interrogados em salas separadas, é mais fácil detectar um Provador malicioso tentando enganar o verificador se houver outro Provador que possa confirmar isso. Na verdade, é tão útil que Babai, Fortnow e Lund foram capazes de provar que MIP = NEXPTIME , a classe de problemas não determinísticos solucionáveis ​​por máquina em tempo exponencial , uma classe muito grande. Além disso, todas as linguagens em NP têm prova inconsciente em um sistema MIP , mesmo sem suposições adicionais; este é um resultado conhecido para IP apenas assumindo a existência de funções unilaterais.

IPP

IPP ( Unbounded IP ) é uma variante de IP em que o verificador BPP é substituído por um verificador PP . Mais precisamente, modifica-se as condições de completude e de correção da seguinte forma:

• Completude  : se uma string está no idioma, o verificador honesto se convencerá disso com uma probabilidade de pelo menos 1/2;
• Correção : se a string não estiver no idioma, nenhum provador será capaz de convencer o verificador honesto de que está com uma probabilidade maior que 1/2.

Embora IPP seja igual a PSPACE , os protocolos IPP se comportam de maneira bem diferente daqueles do IP para oráculos  : IPP = PSPACE para todos os oráculos, enquanto IP ≠ PSPACE para alguns oráculos.

QIP

QIP é uma versão do IP onde o verificador BPP é substituído por um verificador BQP , onde BQP é a classe de problemas decidíveis por computadores quânticos em tempo polinomial. As mensagens são compostas de qubits.

Kitaev e Watrous mostram que QIP está incluído em EXPTIME . Em 2009, Jain, Ji, Upadhyay e Watrous demonstraram que QIP também é igual a PSPACE , o que implica que isso não adiciona força ao protocolo.

compIP

Enquanto IPPP e QIP dão mais poder ao verificador, um sistema compIP ( Sistema de Evidência de IP Competitivo ) enfraquece a condição de completude de uma forma que enfraquece o Provador:

• Completude : se a string estiver na linguagem L , o verificador honesto será convencido disso por um provador honesto com probabilidade de pelo menos 2/3. Além disso, o Prover deve fazê-lo probabilitistically em tempo polinomial por ter um oráculo na L idioma .

Principalmente, isso faz do Prover uma máquina BPP com um oráculo sobre a linguagem, mas apenas no caso de completude, não no caso de correção. A ideia é que, se uma linguagem está em compIP , prová-la interativamente é tão fácil quanto decidir. Com o oráculo, o Provador pode facilmente resolver o problema, mas seu poder limitado torna muito mais difícil convencer o verificador de qualquer coisa. Na verdade, compIP nem mesmo é conhecido ou considerado como contendo NP .

No entanto, esse sistema pode resolver alguns problemas considerados difíceis. Paradoxalmente, mesmo que não se pense que tal sistema seja capaz de resolver todos os NP , ele pode resolver facilmente todos os problemas NP-completos graças à sua autorredutibilidade. Isso vem do fato de que se a linguagem L não é NP- difícil, o Provador é fortemente limitado em seu poder (uma vez que ele não pode mais resolver todos os problemas NP com seu oráculo).

Além disso, o problema de nonisomorfismo de grafos (que é um problema clássico em IP ) também está em compIP , uma vez que a única operação difícil com a qual o Provador pode ser satisfeito é o teste de isomorfismo, para o qual ele pode usar um oráculo para. Solve. Os problemas de residualidade quadrática e isomorfismo de gráfico também estão em compIP . Observe que a não residualidade quadrática (QNR) é provavelmente um problema mais simples do que o isomorfismo de gráfico, uma vez que QNR está em UP intersect co-UP .

Notas e referências

• (fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado "  IP (complexidade)  " ( ver a lista de autores ) .

1. Goldwasser, Micali e Rackoff 1985 .
2. Goldwasser, Micali e Rackoff 1989 .
3. Babai 1985 .
4. Adi Shamir , “  IP = PSPACE  ”, J. ACM , vol.  39, n o  4,Outubro de 1992, p.  869-877 ( ISSN  0004-5411 , DOI  10.1145 / 146585.146609 , ler online , acessado em 11 de julho de 2019 )
5. Carsten Lund , Lance Fortnow , Howard Karloff e Noam Nisan , “  Algebraic Methods for Interactive Proof Systems  ”, J. ACM , vol.  39, n o  4,Outubro de 1992, p.  859-868 ( ISSN  0004-5411 , DOI  10.1145 / 146585.146605 , ler online , acessado em 11 de julho de 2019 )
6. Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos. Sobre integridade e solidez em sistemas de prova interativos . Advances in Computing Research: A Research Annual , 5: 429-442. 1989
7. R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan e P. Rohatgi. A hipótese do oráculo aleatório é falsa . Journal of Computer and System Sciences , 49 (1): 24-39. 1994.
8. J. Watrous. PSPACE tem sistemas de prova interativa quântica de círculo constante . Proceedings of IEEE FOCS'99 , pp. 112-119. 1999.
9. A. Kitaev e J. Watrous. “  Paralelização, amplificação e simulação de tempo exponencial de sistemas de prova interativa quântica  ” ( Arquivo • Wikiwix • Archive.is • Google • O que fazer? ) . Proceedings of ACM STOC'2000 , pp. 608-617. 2000.
10. (em) Autor Desconhecido "  QIP = PSPACE  "2009. .
11. (em) Shafi Goldwasser e Mihir Bellare , "  The Complexity of Decision versus Search  " [PDF] , SIAM Journal on Computing , Volume 23, N o  1 de fevereiro de 1994.
12. Cai JY, Threlfall RA, 2004. "Uma nota sobre residuosidade quadrática e UP ." Cartas de processamento de informações 92 (3): 127-131.

Bibliografia

• László Babai , "Trading group theory for randomness" , em Proceedings of Seventeenth ACM Symposium on the Theory of Computation (STOC) , Providence (Rhodes Island), ACM,1985( leia online ).
• Shafi Goldwasser , Silvio Micali e Charles Rackoff , “A complexidade do conhecimento dos sistemas de prova interativos” , em Proceedings of Seventeenth ACM Symposium on the Theory of Computation (STOC) , Providence (Rhodes Island), ACM,1985( leia online ) , p.  291-304. Resumo detalhado .
• Shafi Goldwasser , Silvio Micali e Charles Rackoff , “  A complexidade do conhecimento dos sistemas de prova interativa  ”, SIAM Journal on Computing , Filadélfia, Society for Industrial and Applied Mathematics , vol.  18, n o  1,1989, p.  186–208 ( ISSN  1095-7111 , DOI  10.1137 / 0218012 , ler online )

links externos

• (pt) A classe IP no Zoológico de Complexidade
• ( fr ) A classe MIP no Complexity Zoo
• ( fr ) Classe IIP no Zoológico de Complexidade
• ( fr ) A classe QIP no Complexity Zoo

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">