avaliação do circuito

13

É sabido se o problema de avaliação do circuito está em N C 1 ? Que tal A L o g T i m e (uniforme N C 1 )?NC1NC1ALogTimeNC1

Sabemos que os circuitos de profundidade podem ser avaliados com circuitos de profundidade k + c, onde c é uma constante universal. Isso significa que os circuitos de profundidade k lg n + o ( lg n ) podem ser avaliados por um circuito de profundidade O ( lg n ) . No entanto, O ( lg n ) não contém uma função que eventualmente domine todas as funções em O ( lg n ) .kk+ccklgn+o(lgn)O(lgn)O(lgn)O(lgn)

Sabemos que o problema de avaliação da fórmula está em . Todo circuito N C 1 é equivalente a uma fórmula booleana. Não podemos calcular a representação de conexão estendida de uma fórmula booleana equivalente daquela de um dado circuito N C 1 em A L o g T i m e ?ALogTimeNC1NC1ALogTime

A representação de conexão estendida de um circuito inclui

  • o número de portas no circuito,
  • o tipo de cada portão e
  • para cada portão e todo caminho π no DAG do circuito, o portão alcançava a partir do g caminho seguinte π .gπgπ

Um caminho é dado por uma sequência 0/1, em que 0 representa o movimento para o pai esquerdo e 1 representa o movimento para o pai direito. Observe que o número de caminhos é polinomial: o comprimento dos caminhos é limitado pela profundidade do circuito.

Kaveh
fonte
4
Tanto quanto eu sei, a avaliação de não é conhecida em N C 1 e é conjecturada como estando fora de N C 1 . Veja "Sobre teorias da aritmética limitada para N C 1 ", E. Jerabek, Ann. Pure Appl. Lógica 2011 ( math.cas.cz/~jerabek/papers/vnc.pdf ). NC1NC1NC1NC1
Iddo Tzameret 21/10
1
@IddoTzameret Talvez você deva fazer do seu comentário uma resposta.
Dai Le
2
O que você quer dizer com avaliação do circuito NC1? Você quer dizer que a entrada dada ao avaliador é um circuito cuja profundidade é delimitada por c log ( n ) para alguma constante fixa c , onde n é o número de entradas para C ? Cclog(n)cnC
Igor Shinkar
@ Igor, bom ponto. Eu tenho que pensar e esclarecer.
Kaveh
@igor, acho que podemos assumir que a profundidade do circuito é para alguma constante arbitrária, mas fixa c 1, pois isso é difícil para N C 1 sob reduções de A C 0 . clgnc1NC1AC0
Kaveh

Respostas:

11

Tanto quanto eu sei, a avaliação de não é conhecida em N C 1 e é conjecturada como estando fora de N C 1 . VejoNC1NC1NC1

Iddo Tzameret
fonte
1
Obrigado Iddo. Estou olhando para o jornal de Emil e é muito útil. Ele afirma que não se sabe que o problema esteja em se usarmos representação de conexão direta, mas é em N C 1 se usarmos representação de conexão estendida . NC1NC1
Kaveh
Ele continua afirmando que o seguinte problema é a dificuldade principal de calcular a avaliação do circuito (com representação dc): Dado um gráfico direcionado G em n vértices com grau externo delimitado, vértices x , y G e um número d log n , determine se y é acessível a partir de x na maioria dos d passos. NC1Gnx,yGdlognyxd
Kaveh
1
@Kaveh, você também pode olhar para "Ampliando limites inferiores por meio de auto-redutibilidade", de Allender e Koucky (JACM 2010). Eles também afirmam que o problema de avaliação não é conhecido em N C 1 . NC1NC1
Iddo Tzameret 22/10/2013
1
Na verdade, essa linha foi a inspiração para minha pergunta. Eu achava que deveria estar em se usarmos representação de conexão estendida e o artigo de Emil afirma que sim. NC1
Kaveh 22/10/2013