É 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 )?
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 ) .
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 ?
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 π .
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.
Respostas:
Tanto quanto eu sei, a avaliação de não é conhecida em N C 1 e é conjecturada como estando fora de N C 1 . VejoNC1 NC1 NC1
fonte