Quais

A famosa Imagem do Mundo de Neil Immerman é a seguinte (clique para ampliar):

Sua classe "Verdadeiramente viável" não inclui nenhuma outra classe; minha pergunta é então:

O que é um problema de AC ⁰ considerado não prático e por quê?

cc.complexity-theory circuit-complexity Michaël Cadilhac
fonte

Talvez um problema que exija circuitos de profundidade 10 ^ {10 ^ 100}?

Tsuyoshi Ito

@ Ross: Acho que não, porque ele não mencionou o “mundo real” e perguntou “por que”; Penso que o meu comentário anterior responde pelo menos à parte do "porquê". No entanto, é certo que não tenho um exemplo de problemas "naturais" que estão em AC0 e exigem circuitos de profundidade 10 ^ {10 ^ 100}.

Tsuyoshi Ito

Existem inúmeros problemas interessantes do mundo real que poderiam ser resolvidos em tempo e espaço constantes (em praticamente qualquer modelo de computação), mas as pessoas agora têm idéia de como resolvê-los na prática. Exemplos extremos estão computando certas constantes; poderíamos codificar a resposta certa (por exemplo, 0 ou 1), mas ainda não sabemos a resposta.

Jukka Suomela

Jukka: essas são instâncias de problemas. As equações diofantinas (como as de Fermat) são indecidíveis como classe, mesmo que instâncias individuais que decidimos realmente tenham circuitos de profundidade constantes.

András Salamon

@ András: Se você prefere problemas de decisão com infinitas instâncias "sim" e "não": Seja

composto por todos os números pares e

, onde

L

$L$

x

$x$

se o jogador branco tem uma estratégia vencedora no xadrez e de outra forma

. Trivialmente, existe uma família muito simples de circuitos que decide

, mas eu ainda diria que é "impraticável". Não porque o circuito seria enorme, mas porqueprojetaro circuito seria um enorme esforço computacional ... Cheating -?)

x = 1

$x = 1$

x = 3

$x = 3$

L

$L$

Jukka Suomela

Respostas:

Se você deseja um exemplo de uma função AC ⁰ que requer profundidade e não pode ser calculada por circuitos AC ⁰ de profundidade $d$ , tente as funções Sipser . O sobrescrito é a profundidade necessária para umcircuitoAC^{0 de}tamanho polinomial. Com a profundidade , o circuito precisaria exponencialmente de muitos portões. $d-1$ $S^{d,n}$ $d$ $d-1$

Portanto, calcular para não seria "verdadeiramente viável". $S^{d,n}$ $d = 10^{10^{100}}$

EDIT: Sua pergunta também pergunta por que isso não seria viável. Eu acho que a razão é que é mais do que o número de átomos no universo visível. $10^{10^{100}}$

Robin Kothari
fonte

Isso é ótimo, obrigado! Talvez você possa adicionar uma definição informal das funções do Sipser? Eu não sabia sobre esse nome.

Michaël Cadilhac

@ Michaël: Infelizmente não tenho uma boa definição intuitiva para as funções do Sipser. A idéia é fazer uma função de quantificadores d de modo que nenhum circuito d-1 de profundidade possa computá-lo. Então, queremos que os quantificadores d quantifiquem sobre um número muito grande de variáveis. Há um belo artigo de Iddo Tzameret, intitulado "Separação de circuitos de profundidade constante usando funções Sipser de Håstad" ( itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf ) que define as funções formalmente na página 7.

Robin Kothari

Toda essa hierarquia é intencionalmente robusta sob alterações polinomiais do tamanho da entrada. Qualquer classe nele pode, portanto, conter funções cuja complexidade é, digamos n ^ {1000000000}, que seria teoricamente "viável", mas certamente não é praticamente isso. Estes, no entanto, provavelmente serão problemas muito artificiais. Em particular, por um argumento de contagem, existe uma família de fórmula DNF (= AC ^ 0 profundidade 2 circuitos) de tamanho n ^ 1000000 que nenhum algoritmo cujo tempo de execução seja menor que n ^ 999999 pode calcular. (Em um ambiente uniforme, esperamos algo semelhante, mas não podemos provar isso.)

Noam
fonte

O problema de parada quando a entrada é representada em unário está em AC ^ 0 e, no entanto, é bastante inviável na realidade. Não sei se foi isso que você quis dizer, mas poderia ser o que Immerman quis dizer.

Elad
fonte

Eu acho que as classes no diagrama são definidas com alguma noção de uniformidade? Caso contrário, a direção ascendente não representaria contenção, pois P não contém AC ^ 0 não uniforme.

Robin Kothari

A C^{0}

$AC^0$

{0, 1}

$\{0,1\}$

{0, m a x; X, B I T, \leq, =}

$\{0,max; X,BIT,\le,=\}$

X

$X$

Ponto bem tomado. Como alternativa, seguindo Erdos, pode-se sugerir o problema de que, para qualquer entrada, gera o número de Ramsey para seis vermelhos e seis azuis.

Elad