Prova interativa para HORN-SAT?

10

Existe uma maneira de um provador convencer um verificador de que alguma expressão HORN-SAT é satisfatória?

Claro que isso pode parecer bobagem, já que existem algoritmos de tempo lineares para o HORN-SAT. Por outro lado, HORN-SAT é P-completo, o que significa que não possui algoritmos de espaço de log, a menos que P = L. Portanto, restrinja as habilidades computacionais do verificador a L. Agora, o verificador é muito fraco, para que o problema não seja mais tolo.

Outra reviravolta nisso é se pode ser uma prova de zero conhecimento.

cc.complexity-theory interactive-proofs zero-knowledge Shaun Harker
fonte
11
No caso de conhecimento que não seja zero, acho que a verificação ingênua usando uma atribuição de verdade satisfatória como certificado requer apenas espaço de log, desde que a entrada e o certificado sejam gravados em fitas somente leitura que não contam como espaço.
Tsuyoshi Ito
@ Tsuyoshi: Não vejo como fazer a verificação ingênua apenas no espaço de log. Se pudéssemos, isso não mostraria que HORN-SAT está em NL e, portanto, por completude P, daria P = NL?
Shaun Harker
Não. Supus que o certificado esteja em uma fita somente leitura, diferente da verificação realizada pela NL.
Tsuyoshi Ito
@Tsuyoshi: Ah, então você pode ler o certificado várias vezes, enquanto uma definição de NL baseada em certificado teria um certificado que só pode ser lido uma vez.
Shaun Harker

Respostas:

11

Esta http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf pesquisa de Anne Condon contém muitos fatos sobre sistemas de prova interativa com espaço limitado.

Existem vários modelos, e as principais diferenças são se você permite moedas privadas apenas para o verificador (IP) ou moedas públicas (AM) e se também restringe o tempo de verificação ao polinômio (não implícito no espaço limitado).

Sem a restrição de tempo, a resposta é sim: IP (espaço de log) contém EXP e AM (espaço de log) = P.

Observe que o IP (espaço de log) provavelmente é maior que o IP padrão. Por outro lado, IP (espaço de log, poly-time) = IP = PSPACE.

AM (log-space, poly-time) = P devido a 'Delegação da computação: provas interativas para trouxas' por Goldwasser et al., STOC 2008.

Além disso, o artigo 'Conhecimento zero com verificadores de espaço de log' de Kilian (FOCS 88) mostra como obter um sistema à prova de conhecimento de zero tempo no tempo de log de espaço de log para tudo em IP (com moedas privadas obviamente).

Hartmut Klauck
fonte
11
Também encontrei um artigo intitulado Delegando Computação: Provas Interativas para Trouxas . O Teorema 3 deste trabalho mostra que AM (espaço logarítmico, tempo poli) = P?
Shaun Harker
Sim, eles realmente mostram isso!
Hartmut Klauck