Problema técnico com a prova do teorema do PCP

12

Estou lendo a prova daqui e me deparei com um problema técnico (ainda que crucial). Eu sei que isso é bastante específico e o contexto é problemático, mas eu não consegui descobrir isso sozinho.

Nas páginas 51 e 55, depois de apresentar os verificadores "padrão", eles se voltam para modificar os verificadores para verificar as atribuições divididas.

No primeiro caso (p. 51), eles verificam se f1,,fk são 0.01 próximos ao código polinomial e depois usam a Algebraization (+ Zero-Testers) para construir uma família de polinômios (com uma Soma -verificar propriedade relacionada com a fórmula de entrada) que cada um deles pode ser avaliada em um ponto determinado 3 valores de cada um dos f~1,,f~k (as palavras de código do código de polinómio armário para f1,,fk ).

No segundo caso (p. 55) que verificam que f1,,fk são 0.01 -close para ser linear, e, em seguida, elas definem uma função f a ser uma soma especial de f~1,,f~k tal que f pode ser avaliada em um ponto dado valores de cada um dos f~1,,f~k (as funções lineares armário para f1,,fk ).

Em ambos os casos, eles realizam testes (Sum-Check ou Tensor + Hadamard) nos valores de um polinômio aleatório na família / f~ .

Meu problema é que o processo de reconstrução dos valores requeridos de cada um f~i pode fornecer valores incorretos com alguma probabilidade constante não negligenciável . Além disso, a probabilidade de que todos os valores sejam reconstruídos corretamente é muito baixa, apenas ck para alguma constante c . E isso é verdade para os dois casos.

Isso pode ser ruim como alguns dos passos dos verificadores necessitam para obter os valores da função de destino f / um polinômio do whp família

Portanto, precisamos ampliar a probabilidade de sucesso usando repetidamente o "procedimento algébrico de reconstrução" alguns tempos O(logk) para cada f~i .

Agora, isso significa que o aumento na complexidade da consulta da sub-rotina (relativamente à complexidade da consulta dos verificadores originais) é um pouco maior que k , ou seja, é O(klogk) (em contraste com o " garantido "-" desejado " O(k) explosão na declaração dos teoremas).

Isso é um problema ou estou faltando alguma coisa (que provavelmente estou)?

Don Fanucci
fonte
Desculpe se isso deve ser óbvio, mas onde está a afirmação dos teoremas pedindo uma explosão de ? Com base em uma leitura superficial, k parece ser um número inteiro constante fixo (não é?). O(k)k
Clement C.
k
Justo, é usado para p=Q(n)Q(n)=1logk
p

Respostas:

1

A complexidade da consulta usada neste artigo é O(1)O(poly(logn))

O(1)

O(poly(f(n)))

O(1)

Lem n
fonte