Circuito comparador
Na teoria da complexidade computacional, CC (circuito comparador) é a classe de complexidade que contém problemas de decisão que podem ser resolvidos por circuitos comparadores de tamanho polinomial.
Circuitos comparadores são redes em que cada um dos pórticos de comparação é direcionado, cada fio é inicializado com uma variável de entrada, a sua negação, ou uma constante, e um dos fios é distinguido como o fio de saída.
O problema mais importante, que é completa para CC é uma variante decisão do problema da união estável.
Definição
editar
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.[1] Uma definição equivalente[2] é a classe de problemas AC0 redutível a CCVP.
Um exemplo, uma rede de classificação podem ser usada para calcular designando o fio do meio como um fio de saída:
Se o fio do meio é designado como saída e os fios são anotados com 16 variáveis de entrada diferentes, então o circuito comparador resultante calcula maioria. Uma vez que existem redes que pode ser construído de AC0, isto mostra que a função da maioria é em CC.
Problemas CC-completo
editarUm 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[3] veio com um algoritmo diferente mostrando que o problema está no CC. O problema é também CC-completa.
Another problem which is CC-complete is lexicographically-first maximal matching.[3] In this problem, we are given a bipartite graph with an order on the vertices, and an edge. The lexicographically-first maximal matching is obtained by successively matching vertices from the first bipartition to the minimal available vertices from the second bipartition. The problem asks whether the given edge belongs to this matching.Outro problema que é CC-completo é o problema primeiro-lexicográfico "matching" máxima. Neste problema, dado um grafo bipartido com uma ordem nos vértices, e uma borda. A primeira correspondência lexicográfica máxima é obtida por vértices do primeiro bipartição sucessiva correspondentes aos vértices mínimas disponíveis a partir da segunda bipartição. O problema pergunta se a borda dado pertence a esse correspondente.
Scott Aaronson mostrou que o modelo de seixos é CC-completo.[4] Neste problema, estamos dado um número de seixos (codificado em unary) e uma descrição de um programa que pode conter apenas dois tipos de instruções: combinar duas pilhas de tamanhos Y e Z para obter uma nova pilha de tamanho y + z , ou dividir uma pilha de tamanho y em pilhas de tamanho e . The problem is to decide whether any pebbles are present in a particular pile after executing the program. Ele usou isso para mostrar que o problema de decidir se as bolas chegar a um vértice pia designado em um dispositivo Digi-Comp II-é também CC-completa.
Contenções
editarO 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,[3] 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.
Referências
- ↑ E. W. Mayr, A. Subramanian (1992). «The complexity of circuit value and network stability». Journal of Computer and System Sciences. 44 (2): 302–323. doi:10.1016/0022-0000(92)90024-d
- ↑ S. A. Cook, Y. Filmus, D. T. M. Le (2012). «The complexity of the comparator circuit value problem». arXiv:1208.2721
- ↑ a b c A. Subramanian (1994). «A new approach to stable matching problems». SIAM Journal on Computing. 23 (4): 671–700. doi:10.1137/s0097539789169483
- ↑ Aaronson, Scott (4 de julho de 2014). «The Power of the Digi-Comp II». Shtetl-Optimized. Consultado em 28 de julho de 2014
Ligações externas
editar- Complexity Zoo: CC