Provando limites inferiores provando limites superiores

29

O recente resultado do limite inferior da complexidade do circuito de Ryan Williams fornece uma técnica de prova que usa o resultado do limite superior para provar os limites inferiores da complexidade. Suresh Venkat, em sua resposta a esta pergunta, existem resultados contra-intuitivos em ciência da computação teórica? , forneceu dois exemplos de estabelecimento de limites inferiores comprovando os limites superiores.

  • Quais são os outros resultados interessantes para provar limites inferiores de complexidade que foram obtidos provando limites superiores de complexidade?

  • Existe alguma conjectura limite superior que implicaria (ou P N P )?NPP/polyPNP

Mohammad Al-Turkistany
fonte
Isso deveria ser uma CW?
Mohammad Al-Turkistany
Eu gosto como está (não CW), mas acredito que é um [soft-question].
MS Dousti 21/11/2010
2
@Sadeq: não pense que esta é uma pergunta suave, isso é preciso o suficiente para ter uma resposta clara.
Kaveh
Resultado de Meyer apontado por Suresh mostra que a existência de circuitos polinomiais para provaria P N P . EXPPNP
Mohammad Al-Turkistany

Respostas:

23

Pode-se inverter a questão e perguntar o que os limites inferiores não são provados ao provar um limite superior. Quase todos os limites inferiores da complexidade da comunicação (e os limites inferiores do algoritmo de streaming e os limites inferiores da estrutura de dados que dependem dos argumentos da complexidade da comunicação) são comprovados mostrando que um protocolo de comunicação pode ser transformado construtivamente em um esquema de codificação, com o comprimento da codificação dependendo do complexidade de comunicação do protocolo e o limite inferior do protocolo decorre do fato de que você não pode codificar todas as mensagens de n bits usando n-1 bits ou menos.

Os limites inferiores do circuito Razborov-Smolensky funcionam mostrando como simular circuitos de profundidade limitada por polinômios de baixo grau.

Alguns candidatos de limites inferiores que não são provados com um limite superior podem ser o teorema da hierarquia de tempo (embora, para obter os limites mais rígidos, seja necessário uma máquina de turing universal eficiente, que é uma tarefa algorítmica não trivial) e a prova dos limites inferiores de AC0 usando o lema de comutação (mas a prova mais limpa do lema de comutação usa uma complexidade de contagem / incompressibilidade / Kolmogorov)

Luca Trevisan
fonte
11
14

logn

Suresh Venkat
fonte
10
Se você considerar a dureza NP (em oposição à separação de uma classe) como limites inferiores, não precisará do teorema do PCP; reduções são algoritmos eficientes que provam que alguns problemas são difíceis.
Tsuyoshi Ito 23/11
esse é um bom ponto, Tsuyoshi. No entanto, as reduções da dureza NP são "diretas". mostre que resolver um problema desconhecido resolve um problema difícil conhecido. Alguns dos exemplos dados aqui são mais indiretos. Mas isso é subjetivo, é claro.
Suresh Venkat
3
A própria afirmação do teorema do PCP é a completude do NP do Gap-3SAT. Além disso, não sei o que você quis dizer ao afirmar que o teorema do PCP é indireto. É verdade que o teorema do PCP requer uma das provas mais complicadas entre os resultados de completude do PN, mas é uma coisa boa?
Tsuyoshi Ito 23/11
Suresh, você poderia postar aqui, como uma nova resposta, uma versão expandida dos dois exemplos que você referenciou na sua resposta à outra pergunta (resultado de Meyer e GCT)?
Mohammad Al-Turkistany
qualquer razão para isso? Não tenho problemas para fazê-lo, mas é necessário, pois você o cita na pergunta?
Suresh Venkat
12

O método de incompressibilidade é um método baseado na complexidade de Kolmogorov para provar limites mais baixos. Uma das primeiras aplicações desse método foi provar que o reconhecimento de palíndromos em uma máquina de Turing com uma única fita requer tempo quadrático.

Em termos gerais, a idéia desse método é descrever um procedimento para encontrar uma entrada usando as informações contidas na execução de um algoritmo que resolve o problema que consideramos nessa entrada. Quanto melhor for o procedimento, maior será o limite inferior do problema original.

Obviamente, todos os detalhes podem ser encontrados no livro de Li e Vitanyi .

Marc
fonte
11

Para a pergunta "limite inferior via limite superior", você perguntou:

O artigo do STOC 2010 "Como comprimir a comunicação interativa" [BBCR10] chega a um teorema de soma direta aprimorado para complexidade de comunicação aleatória, demonstrando um protocolo de compressão aprimorado para comunicação interativa.

CIO~(CI)

fnkfkn

Daniel Apon
fonte
7

De alguma forma, isso é diferente do que você pediu, mas, como está relacionado, pensei em mencionar.

Carter e Wegman (1977) introduziram a noção de hash universal . A noção foi usada em vários artigos ( Sipser (1983) , Stockmeyer (1983) , Babai (1985) e Goldwasser & Sipser (1986) ) para provar limites inferiores aproximados .

Isso foi até 1987, no qual Fortnow fez uso do hash universal para provar os limites superiores aproximados . (De fato, para fornecer um protocolo para provar os limites superiores aproximados.)


Editar:

Estes não são resultados de limite inferior, mas podem ser úteis de qualquer maneira:

NPP/polyPH=Σ2p=Π2p

NPP/polyAM=MA

coNPNP/polyPH=Σ3p=Π3p

MS Dousti
fonte
5

PNP

CC1Cm

PNP

Mohammad Al-Turkistany
fonte
5

Aqui está um exemplo de Complexidade computacional: uma abordagem moderna de Arora e Barak (página 128):

EXPo(2n/n)PNP

Mohammad Al-Turkistany
fonte