Existe uma explicação para a dificuldade de provar limites inferiores quadráticos para problemas interessantes de DN?

Este é um acompanhamento da minha pergunta anterior:

Limite inferior da complexidade determinística do tempo mais conhecido para um problema natural em NP

Acho desconcertante não termos sido capazes de provar qualquer limite determinístico quadrático de tempo para qualquer problema de NP interessante com o qual as pessoas se preocupam e tentam projetar algoritmos melhores. Nossa conjectura de Hipótese de tempo exponencial afirma que o SAT não pode ser resolvido no tempo determinístico subexponencial, mas ainda não podemos provar que o SAT (ou qualquer outro problema de NP interessante) requer tempo quadrático!

Eu sei que interessante é um tanto subjetivo e vago. Eu não tenho uma definição. Mas deixe-me tentar descrever o que considero um problema interessante: estou falando de problemas que mais do que algumas pessoas acham interessantes. Não estou falando de problemas isolados, projetados principalmente para responder a uma pergunta teórica. Se as pessoas não estão tentando encontrar algoritmos mais rápidos para um problema, é uma indicação de que o problema não é tão interessante. Se você quiser exemplos concretos de problemas interessantes, considere os problemas no artigo de Karp, de 1972, ou em Garey e Johnson, 1979 (a maioria).

Existe alguma explicação para o motivo de não termos sido capazes de provar um limite determinístico quadrático do tempo para qualquer problema interessante de NP?

cc.complexity-theory lower-bounds big-picture barriers Anônimo
fonte

Porque limites mais baixos são difíceis? Que tipo de explicação o satisfaria?

27413 Jeff Jeff

@ Jɛ how E as explicações não triviais que são informativas e esclarecedoras? Intuições ou resultados explicando por que estamos presos onde estamos para provar limites inferiores. Como nossas reivindicações foram muito mais fortes do que nossos resultados, tenho certeza de que outros especialistas pensaram sobre o motivo por que, após décadas de tentativas, não conseguimos obter um limite quadrático inferior para um problema interessante de NP.

Anônimo

Aqui está uma explicação do blog de Lipton; Isca e Switch: Por que os limites inferiores são tão difíceis? rjlipton.wordpress.com/2009/02/12/…

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Eu acho que a visão de Rudich, como no blog de Lipton, poderia ser uma resposta, não apenas um comentário. Especialmente porque esse argumento, diferentemente de outros, se aplica igualmente a limites inferiores limites inferiores super-polinomiais.

n^{2}

$n^2$

Joshua Grochow

A questão dos limites inferiores do tempo quadrático é relevante quando você restringe os algoritmos a ter muito pouco espaço (por exemplo, polilog) ou quando você olha para máquinas Turing de uma fita (que têm acesso muito restrito à memória). Porém, quando a memória é irrestrita e o acesso à memória é irrestrito, a questão "real" é se há limites super lineares de tempo super lineares para problemas interessantes de PN, em qualquer modelo computacional de acesso aleatório. (Grandjean provou alguns super-linear limites inferiores para as máquinas de Turing multitape, mas eles contam com a estrutura de fitas unidimensionais.)

Ryan Williams

Respostas:

Aqui está uma explicação do blog de Lipton: Bait and Switch: Por que os limites inferiores são tão difíceis?

Como observou Grochow, o insight de Rudich se aplica igualmente a limites inferiores e a limites polinomiais superpolinomiais. $n^2$

O insight de Rudich explica por que qualquer prova de limite inferior de que é baseada no método a seguir não pode funcionar.

"qualquer cálculo que calcule deve progredir lentamente em direção a . Cada passo computacional pode apenas chegar um pouco mais perto do objetivo final; portanto, o cálculo terá muitos passos." $f$ $f$

Basicamente, não há nenhuma medida de progresso que possa sobreviver ao truque Bait and Switch de Rudich e leve com sucesso a um limite inferior.

Mohammad Al-Turkistany
fonte

Você pode encontrar outra visão do argumento "isca e troca" no capítulo de provas naturais de Arora-Barak. Eles usam o mesmo argumento para argumentar que um argumento de limite inferior do estilo "medida formal de complexidade" deve ser aplicado a funções aleatórias com alta probabilidade. Mas se uma medida formal de complexidade

atribui alta complexidade a uma função aleatória
não atribui alta complexidade a uma função fácil
pode ser facilmente calculado a partir da tabela verdade de uma função

então pode ser usado para quebrar geradores pseudo-aleatórios. É isso que a barreira das provas naturais é, informalmente. Argumentamos que 1. é muito razoável para muitas abordagens para limites mais baixos, sem 2. a medida de complexidade parece inútil e 3. é baseada na observação de que conseguimos transformar a maioria das provas combinatórias de existência em algoritmos eficientes e no intuição de que uma prova inerentemente não construtiva é difícil de conceber.

Você pode tornar o exposto mais concreto criando geradores pseudoaleatórios muito eficientes. Se uma função pode ser calculado dentro de uma complexidade que a aparência pseudo-aleatórios para funções de uma classe'em seguida, uma medida computável dentro está condenado para lowerbounds contra . $C$ $C'$ $C'$ $C$

Sasho Nikolov
fonte