Os circuitos AND & OR estão completos P?

21

O portão AND & OR é um portão que recebe duas entradas e retorna seu AND e seu OR. Os circuitos são feitos apenas a partir da porta AND & OR, sem fanout, capazes de realizar cálculos arbitrários? Mais precisamente, o espaço de log da computação do tempo polinomial é redutível aos circuitos AND & OR?

Minha motivação para esse problema é bastante estranha. Como descrito aqui , esta questão é importante para a computação dentro do jogo de computador Dwarf Fortress .

Itai Bar-Natan
fonte
2
Tais circuitos são monótonos e, portanto, estão longe de P-completo.
David Harris
3
@ David Harris: À primeira vista, eu também pensava assim, mas esse raciocínio não está correto porque uma redução no espaço de log pode aumentar a entrada com sua negação!
Tsuyoshi Ito
2
Pode ser, note que a avaliação monótona da fórmula booleana está completa para em A C 0 . NC1AC0
Kaveh

Respostas:

23

Se eu não entenda mal o que você quer dizer com E & OR gate, que é basicamente uma porta de comparação que leva dois bits de entrada e y e produz dois bits de saída x y e x y . Os dois bits de saída x y e x y são basicamente min ( x , y ) e max ( x , y ) .xyxyxyxyxy(x,y)(x,y)

Os circuitos do comparador são construídos compondo esses portões do comparador, mas não permitindo mais fan-outs além das duas saídas produzidas por cada porta . Assim, podemos desenhar circuitos comparadores usando as notações abaixo (da mesma forma que desenhamos redes de classificação).

insira a descrição da imagem aqui

Podemos definir o problema do valor do circuito comparador (CCV) da seguinte maneira: dado um circuito comparador com entradas booleanas especificadas, determine o valor de saída de um fio designado. Ao considerar o fechamento desse problema de CCV sob reduções de espaço de log, obtemos a classe de complexidade CC , cujos problemas completos incluem problemas naturais como correspondência máxima lex-first, casamento estável e roomate estável.

0

Dai Le
fonte
0

(a resposta não é elegível porque se refere a portas AND, OR separadas sem restrição de fan-out)

O seguinte artigo está no tópico: Autômatos celulares por votação majoritária, Ising Dynamics e P-Completeness

Mostramos que em três ou mais dimensões destes sistemas pode simular circuitos booleanas de portas AND e OR, e são, portanto, P-completo . Ou seja, prever o estado dos intervalos de tempo no futuro é pelo menos tão difícil quanto qualquer outro problema que leva tempo polinomial em um computador serial.

(...)

O problema do valor do circuito monótono, onde os portões AND e OR são permitidos, mas NÃO os portões não são, ainda está P completo pelo seguinte motivo: usando as leis de De Morgan (...), podemos mudar as negações de volta pelos portões até que apenas afetam as próprias entradas. Portanto, qualquer problema de valor do circuito pode ser convertido em um problema de valor do circuito monótono com algumas das entradas negadas. Esse tipo de conversão, de uma instância de um problema para uma instância de outro, é chamado de redução.

Mooncer
fonte
Poderia, por favor, elaborar sua resposta? Não consegui ver a conexão entre "esses sistemas" e os circuitos AND & OR mencionados acima.
Dai Le
Eu li o jornal há 2 anos. Ele é dedicado aos circuitos lógicos monofônicos e de completude-P. Deixo a interpretação final para o leitor, porque não me lembro de detalhes agora. É certamente um bom artigo, especialmente se o Itai parecer confuso. Mais: o texto em negrito na minha citação não é a resposta - que os circuitos lógicos AND / OR estão completos P?
Mooncer 25/03
OK, você está certo. Talvez eu deixe minha resposta, talvez seja útil para alguém.
Mooncer 25/03
3
É um fato bem conhecido que o problema de avaliar circuitos monótonos que consistem em portas AND e portas OR, onde cada porta pode ter fanout 2 , é P-completo. O problema do circuito mencionado pelo pôster original impõe restrições de fanout e, portanto, não se sabe que o P-complete.
Dai Le
2
@vzn A avaliação do circuito está em P. Uma referência para o fato de Dai mencionar é o livro de Cook e Nguyen "Fundamentos lógicos da complexidade da prova".
Yuval Filmus