Circuito comparador

Um circuito comparador é uma rede de fios e portas. Cada porta de comparação, que é uma aresta dirigida conecta dois fios, leva suas duas entradas e saídas na ordem de classificação (o valor maior acaba no fio da borda está sendo apontando). A entrada para qualquer fio pode ser uma variável, a sua negação, ou uma constante. Um dos fios é designado como o fio de saída. A função calculada pelo circuito é avaliada conforme a inicialização dos fios de acordo com as variáveis de entrada, a execução das portas, a fim de comparação, a saída e o valor transportado pelo fio de saída. O problema de valores de circuito comparador (CCVP) é o problema de se avaliar um circuito comparador, dada uma codificação do circuito e a entrada para o circuito. A classe de complexidade CC é definida como a classe de problemas logspace redutível a CCVP. Uma definição equivalente é a classe de problemas AC0 redutível a CCVP.

Imagem: Rvale · BY-SA · Openverse

Um problema em CC é CC-completo se todos problemas de CC pode ser reduzido usando uma redução em logspace. O problema de valoração do circuito comparador (CCVP) é CC-completo. No problema da união estável, existe um número igual de homens e mulheres. Cada pessoa ocupa todos os membros do sexo oposto. A correspondência entre homens e mulheres é estável se não houver nenhum homem não pareado e mulher que preferem se mutuamente sobre os seus parceiros atuais. A combinação estável sempre existe. Entre os "matchings" estáveis, não é aquele em que cada mulher recebe o melhor homem que ela nunca fica em qualquer combinação estável; isto é conhecido como a combinação estável "mulher ideal". Um decisor do problema de correspondência estável é, dado o ranking de todos os homens e mulheres, se um determinado homem e uma mulher são correspondidos dada na combinação estável mulher ideal. Embora o algoritmo de Gale-Shapley clássica não pode ser implementado como um circuito comparador, Subramanian veio com um algoritmo diferente mostrando que o problema está no CC. O problema é também CC-completa.

Imagem: secasema-ali · BY-NC-SA · Openverse

O problema de avaliação circuito comparador pode ser resolvido em tempo polinomial, e assim por CC, está contido em P. Por outro lado, os circuitos de comparação pode resolver acessibilidade dirigido, e assim por CC contém NL. Há um mundo relativizada em que CC e NC são incomparáveis, e assim ambas as contenções são próprias.