A Wikipedia fornece exemplos de problemas em que a versão de contagem é difícil, enquanto a versão de decisão é fácil. Algumas delas estão contando combinações perfeitas, contando o número de soluções para SAT e o número de classificações topológicas.
Existem outras classes importantes (digamos exemplos em treliças, árvores, teoria dos números e assim por diante)? Existe um compêndio de tais problemas?
Existem muitos tipos de problemas em que possuem versões de contagem -hard.
Existe uma versão de um problema natural em que é mais completamente compreendida ou mais simples do que a correspondência perfeita bipartida geral (inclua detalhes sobre por que mais simples, como estar provável nas classes mais baixas da hierarquia e assim por diante) em outras área (como teoria dos números, reticulados) ou, pelo menos, para gráficos bipartidos simples em particular, cuja versão contadora é -hard?
Serão apreciados exemplos de treliças, polítopos, contagem de pontos e teoria dos números .
Respostas:
Aqui está um exemplo verdadeiramente excelente (posso ser tendencioso).
Dado um conjunto parcialmente ordenado:
a) ele possui uma extensão linear (isto é, um pedido total compatível com o pedido parcial)? Trivial: Todos os posets possuem pelo menos uma extensão linear
b) Quantos possuem? # P-complete para determinar isso (Brightwell e Winkler, Counting Linear Extensions , Order, 1991)
c) Podemos gerá-los todos rapidamente? Sim, em tempo amortizado constante (Pruesse e Ruskey, Generating Linear Extensions Fast , SIAM J Comp 1994)
fonte
Um exemplo interessante da teoria dos números está expressando um número inteiro positivo como uma soma de quatro quadrados. Isso pode ser feito com relativa facilidade em tempo polinomial aleatório (veja meu artigo de 1986 com Rabin em https://dx.doi.org/10.1002%2Fcpa.3160390713 ) e, se bem me lembro, agora existe um tempo polinomial determinístico solução. Porém, contar o número de tais representações permitiria calcular a função da soma dos divisores , que é o tempo polinomial aleatório equivalente ao fatoramento n . Portanto, o problema da contagem é provavelmente difícil.σ(n) n
fonte
Um exemplo muito bom e simples da Teoria dos grafos é contar o número de circuitos Eularian em um gráfico não direcionado.
A versão de decisão é fácil (... e o problema das Sete Pontes de Königsberg não tem solução :-)
A versão da contagem é # P-hard: Graham R. Brightwell, Peter Winkler: A contagem de circuitos eulerianos é # P-Complete . ALENEX / ANALCO 2005: 259-262
fonte
Em relação à sua segunda pergunta, problemas como o Monotone-2-SAT (decidir a satisfação de uma fórmula CNF com no máximo 2 literais positivos por cláusula) são completamente triviais (basta verificar se a fórmula está vazia ou não), mas o problema de contagem é # P-difícil. Mesmo aproximar o número de atribuições satisfatórias dessa fórmula é difícil (consulte Sobre a dureza do raciocínio aproximado, Dan Roth, Artificial Intelligence, 1996).
fonte
A partir de [Kayal, CCC 2009] : avaliar explicitamente polinômios aniquilantes em algum momento
Do resumo: `` Este é o único problema computacional natural em que a determinação da existência de um objeto (o polinômio aniquilador em nosso caso) pode ser feita com eficiência, mas a computação real do objeto é comprovadamente difícil ''.
ANNIHILATING-EVAL é -hard. Além disso, o polinômio aniquilador não possui uma representação de circuito pequena, a menos que colapso. A ( t 1 , . . . , T k ) P H#P A(t1,...,tk) PH
fonte