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.
sat
proofs
nondeterminism
argentpepper
fonte
fonte
Respostas:
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 umk -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 , 1 }k 2k ( s + 2k) ⋅ d s C d C . (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# F n m C n / 2 m n mn⋅2n/2 n/2 F 1 F 0 quando é 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 .C 2n/2 2n/2 2n/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 circuitoC 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 k ⋅ d , e Q `` esboços '' a avaliação do grau2k Q(x) K 2n Q(x) 2k⋅d Q circuito aritmético C em todas as 2 k atribuições. O polinômio Q satisfaz duas condições conflitantes:d C 2k Q
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 (Q C αi K , onde um( Q ( α0 0) , Q ( α1) , … , Q ( αK) ) = ( C( um1) , … , C( um2K) )) é a i- ésima atribuição booleana às k variáveis de C (sob alguma ordem nas atribuições).umaEu Eu k C
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.Q C 2k 2k+ 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
fonte