Faz

21

Existe alguma hipótese plausível de complexidade / criptografia que exclua a possibilidade de que os circuitos de tamanho polinomial tenham tamanho subexponencial (isto é, com ϵ < 1 ) de profundidade limitada (2O(nϵ)ϵ<1) circuitos d = O ( 1 ) )?d=O(1)

Sabemos que cada função calculável por um circuito pode ser calculado por um tamanho de 2 O ( n ε ) profundidade d do circuito (usando AND, OR e NOT portas, sem limites fan-in) (para cada 0 < ε existe um d e d pode ser feita para ser O ( 1 / ε ) ).NC12O(nϵ)d0 0<ϵddO(1 1/ϵ)

A questão é:

existe uma razão que tornaria improvável a existência de tais circuitos para circuitos de tamanho polinomial geral?

Kaveh
fonte
3
Se por tamanho subexponencial você quer dizer (em vez de 2 o ( n ) ) e por profundidade delimitada quer dizer profundidade constante, a paridade não possui circuitos de profundidade delimitada de tamanho subexponencial sem suposições. 2no(1 1)2o(n)
MCH
Você deve postar seu comentário como resposta. Você receberá crédito por isso e, se apropriado, poderá ser marcado como uma resposta aceita. Isso também impedirá que a questão seja automaticamente reeditada periodicamente pelo bot da Comunidade.
Suresh Venkat
@MCH, atualizei a pergunta para esclarecer o que quero dizer com tamanho subexponencial.
Kaveh
3
No caso uniforme, você pode dizer algo ( implica tempo limites inferiores para SAT). Porém, no caso não uniforme, não conhecemos limites inferiores fortes para P / poli, nem limites inferiores fortes para sua definição de circuitos de profundidade constante de tamanho subexponencial. Por exemplo, ainda é possível E X P N PTEuME(t)ΣO(d)TEuME[n1 1/d]EXPNPpode ser simulado em qualquer uma dessas classes. Portanto, não tenho certeza do que você poderia concluir. (Por que eu fiz isso um comentário Porque não é realmente uma resposta ...?)
Ryan Williams
2
Bem, é considerada improvável. Sipser (CCC '86) mostrou que P = R P ou T I M E ( t ) S P A C E ( t 1 - ϵ ) para alguns ϵ > 0TIME(t)ATIME(t1ϵ)P=RPTIME(t)SPACE(t1ϵ)ϵ>0, Sob certas hipóteses de construção expansor que foram mais tarde demonstrado ser verdade por Saks, Srinivasan, e Zhou.This foi tomada como evidência de que . Trabalhos posteriores sobre dureza versus aleatoriedade tornaram as conexões mais precisas. P=RP
perfil completo de Ryan Williams

Respostas:

8

O que você pede deve ter consequências ruins, mas não consigo pensar em nenhuma imediatamente. Então, eu tenho apenas algumas dicas para o que sabemos.

Confira o Viola's Sobre o poder da computação em pequena profundidade O melhor que sabemos é a construção da Valiant para circuitos booleanos: registre circuitos lineares de tamanho linear até 3 circuitos subexp. (Conhecemos melhor os circuitos aritméticos .) Há também alguns resultados de Beigel / Tarui no ACC iniciados em circuitos de profundidade limitada de tamanho superpoli. Não me lembro de ter sido estendido a todos os .NC1

V Vinay
fonte
Obrigado pelas dicas interessantes. Estou interessado principalmente na probabilidade de existência de tal simulação (ou seja, conjecturas e hipóteses que implicariam uma resposta negativa ou positiva para e classes semelhantes como N C, onde a resposta não é conhecida incondicionalmente). sabe algo assim? P/poeuyNC
Kaveh
Infelizmente nada. Eu estava pensando em alguns dos documentos antigos de Buhrman / Homer e outros, mas não me lembro de nada desse tipo. Voltará se algo aparecer.
precisa