Como é provada a versão MA do SETH para ser falsa?

13

De acordo com este artigo , que discute uma extensão não determinística da Hipótese do Tempo Exponencial Forte (SETH), "[...] Williams recentemente demonstrou hipóteses relacionadas sobre a complexidade de Merlin-Arthur do k-TAUT são falsas". No entanto, esse documento cita apenas uma comunicação pessoal.

Como é provada a versão MA do SETH para ser falsa?

Suspeito que isso envolva a algebrização da fórmula, mas não tenha mais nenhuma idéia.

argentpepper
fonte
Você poderia postar o documento se receber uma resposta?
13
Um artigo está chegando em breve. Obrigado pela sua paciência.
Ryan Williams
3
Na verdade, direi que o que provo é muito mais forte do que: "existe um protocolo Merlin-Arthur de para refutar o k-TAUT", ou seja, fórmulas insatisfatórias do k-CNF. Você pode obter cerca de 2 n / 2 de tempo para refutar qualquer circuito UNSAT de profundidade sublinear, até onde eu sei. Mas como eu disse, o jornal está chegando em breve. 1.9n2n/2
Ryan Williams
2
Possivelmente pergunta tola, esse resultado (essencialmente) está se movendo em direção à idéia: as conjecturas "NSETH" e "k-TAUT exigem circuitos de tamanho exponencial" são mutuamente exclusivas? Ou a construção do PRG preenche facilmente qualquer possível lacuna entre a complexidade MA e NP do k-TAUT?
21715 Joe
2
Não é uma pergunta boba! Resposta curta é que eu ainda não sei.
Ryan Williams

Respostas:

21

Você pode encontrar uma pré-impressão seguindo este link http://eccc.hpi-web.de/report/2016/002/

EDIT (1/24) Por solicitação, aqui está um resumo rápido, retirado do próprio papel, mas encobrindo muitas coisas. Suponha Merlin pode vir a Arthur que, para um k -variável circuito aritmético , o seu valor em todos os pontos em { 0 , 1 } K é uma determinada mesa de 2 k elementos de campo, com o tempo sobre a ( s + 2 k ) d , onde s é o tamanho de C e d é o grau do polinômio calculado por CC{0 0,1}k2k(s+2k)dsCdC. (Chamamos isso de "prova curta e não interativa de avaliação de lotes" - avaliar em várias atribuições.)C

Então Merlin pode resolver o SAT para Arthur da seguinte maneira. Dado um F CNF em n variáveis ​​e cláusulas m , Merlin e Arthur primeiro constroem um circuito aritmético C em n / 2 variáveis ​​de grau no máximo m n , tamanho em torno de m n 2 n / 2 , que soma uma soma de todas as atribuições a as primeiras n / 2 variáveis ​​do CNF F (adicionando 1 à soma quando F é verdadeiro e 0#FnmCn/2mnmn2n/2n/2F1F0 0quando é falso). Usando o protocolo de avaliação lote, Merlin pode, então, comprovar que leva em 2 n / 2 valores determinados em todas as suas 2 n / 2 atribuições booleanos, em cerca de 2 N / 2 p o l y ( n , m ) tempo. Resumindo todos esses valores, temos a contagem das atribuições do SAT para F .C2n/22n/22n/2poly(n,m)F

Agora dizemos em alto nível como fazer o protocolo de avaliação de lotes. Queremos que a prova seja uma representação sucinta do circuito C que seja fácil de avaliar em todas as entradas fornecidas e também fácil de verificar com aleatoriedade. Definimos a prova como um polinômio univariado Q ( x ) definido sobre um campo de extensão suficientemente grande do campo base K (com característica de pelo menos 2 n para a nossa aplicação), em que Q ( x ) possui um grau de cerca de 2 kd , e Q `` esboços '' a avaliação do grau2kQ(x)K2nQ(x)2kdQ circuito aritmético C em todas as 2 k atribuições. O polinômio Q satisfaz duas condições conflitantes:dC2kQ

  • O verificador pode usar o esboço para produzir eficientemente a tabela verdade de C . Em particular, para alguns α i explicitamente conhecidos da extensão de K , queremos ( Q ( α 0 ) , Q (QCαiK , onde um(Q(α0 0),Q(α1),...,Q(αK))=(C(uma1),...,C(uma2K)) é a i- ésima atribuição booleana às k variáveis ​​de C (sob alguma ordem nas atribuições).umaEuEukC

  • O verificador pode verificar se é uma representação fiel do comportamento de C em todas as atribuições booleanas de 2 k , em aproximadamente 2 k + s , com aleatoriedade. Isso basicamente se torna um teste de identidade polinomial univariada.QC2k2k+s

A construção de usa um truque de interpolação originado das provas holográficas, em que expressões multivariadas podem ser eficientemente `` expressas '' como univariadas. Os dois itens utilizam algoritmos rápidos para manipular polinômios univariados.Q

Ryan Williams
fonte
Na parte centralizada (perto da parte superior) da parte 2 na página 6, parece que R (x) deve ser substituído por R (r).
Por favor, envie comentários sobre o manuscrito diretamente para mim; Não verifico stackexchange todos os dias. Obrigado.
Ryan Williams
5
Você poderia resumir a idéia principal do artigo, a fim de fornecer uma resposta mais independente e possivelmente proteger contra a podridão dos bits?
Cody