Problèmes faciles avec les versions de comptage dur

20

Wikipedia fournit des exemples de problèmes où la version de comptage est difficile, alors que la version de décision est facile. Certains d'entre eux comptent des appariements parfaits, comptant le nombre de solutions à $2$ -SAT et le nombre de tri topologiques.

Existe-t-il d'autres classes importantes (par exemple des exemples dans les réseaux, les arbres, la théorie des nombres, etc.)? Existe-t-il un recueil de ces problèmes?

Il existe de nombreux types de problèmes dans $P$ qui ont des versions de comptage $\#P$ -hard.

Existe-t-il une version d'un problème naturel dans $P$ qui soit plus complètement comprise ou plus simple que la correspondance parfaite bipartite générale (veuillez inclure des détails sur pourquoi plus simple, comme être prouvable dans les classes les plus basses de la hiérarchie $NC$ , etc.) dans d'autres (comme la théorie des nombres, les réseaux) ou au moins pour des graphes bipartites simples particuliers, dont la version de comptage est $\#P$ -hard?

Des exemples de réseaux, polytopes, comptage de points, théorie des nombres seront appréciés .

reference-request counting-complexity nt.number-theory permanent decision-trees T ....
la source

1

Vraisemblablement, vous voulez des problèmes naturels , car [par réduction de #SAT, les problèmes qui # P-dur sous [réductions qui multiplient la réponse par un nombre non nul] ont des problèmes de décision HP-dur] et [par la fonction d'identité, {x: x est 1+ (nombre_de_variables_ (

ϕ

$\phi$ )) ou [un zéro suivi d'une affectation satisfaisante à

ϕ

$\phi$ ]} est # P-difficile sous le type de réduction le plus strict suivant, mais sa version de décision est triviale].

@RickyDemer votre écriture est succincte. Oui, je veux des problèmes naturels.

T ....

Ne comprenons-nous vraiment pas complètement les correspondances parfaites dans les graphiques bipartites? En outre, il existe un algorithme RNC2 pour le problème.

Sasho Nikolov

1

Oui, non. Nous n'avons pas d' algorithme

déterministe

N C

$NC$ .

T ...

8

Voici un exemple vraiment excellent (je peux être partial).

Étant donné un ensemble partiellement ordonné:
a) a-t-il une extension linéaire (c'est-à-dire un ordre total compatible avec l'ordre partiel)? Trivial: Tous les posets ont au moins une extension linéaire
b) Combien en a-t-il? # P-complete pour le déterminer (Brightwell et Winkler, Counting Linear Extensions , Order, 1991)
c) Pouvons-nous tous les générer rapidement? Oui, en temps amorti constant (Pruesse et Ruskey, Generating Linear Extensions Fast , SIAM J Comp 1994)

Gara Pruesse
la source

3

+1: Je suis d'accord pour dire que c'est un excellent exemple (je pensais le publier moi-même et j'ai ensuite vu cette réponse). De plus, de peur que quelqu'un ne dise "Qu'en est-il de décider s'il y a au moins une autre extension linéaire", ce problème est également complètement trivial: une commande totale a 1 extension, tous les autres posets ont> 1. Et détecter exactement 2 extensions est également facile (cela se produit s'il y a exactement une paire d'éléments incomparables). En fait, il existe une classification complète des posets avec jusqu'à 7 extensions linéaires (voir Hanamura-Iwata, IPL 2011 ).

Joshua Grochow du

C'est un bel exemple en effet. Il existe cependant un problème beaucoup plus "simple", mais bénéficiant du même type de propriétés (plus simple dans le sens où ces propriétés sont presque triviales à prouver). Compter le nombre d'affectations satisfaisantes d'un DNF: a) chaque DNF non vide est satisfaisable b) le comptage est # P-complet (réduction à #SAT) c) l'énumération peut être effectuée avec un retard polynomial (un temps amorti peut-être constant, avoir d'y penser)

holf

Je serais très intéressé de savoir si des affectations satisfaisantes DNF peuvent être générées en temps amorti constant (CAT). À l'époque et dans mon article avec Frank, en 1994, les extensions linéaires étaient le premier objet "naturellement défini" pour lequel le comptage était difficile et la génération aussi rapide que possible, lorsqu'elle était amortie (c.-à-d. CAT). Les solutions DNF semblent également être un candidat probable pour cela. Quelqu'un at-il une référence?

Gara Pruesse

@GaraPruesse Je n'ai pas de références pour ça. Pour monotone-DNF, cela équivaut à énumérer un ensemble d'hypergraphes et certaines techniques pour améliorer le retard sont présentées dans "Algorithmes efficaces pour dualiser les hypergraphes à grande échelle" par Keisuke Murakami et Takeaki Uno dl.acm.org/citation.cfm? id = 2611867 . Nous devons vérifier si cela donne CAT. Pour DNF, mon intuition est que s'il y a une petite clause, vous avez déjà suffisamment de solutions pour le forçage brut. Sinon, vous n'avez que des clauses volumineuses et qui sont alors plus susceptibles de se heurter et qui peuvent être utilisées pour concevoir un algorithme CAT.

holf

17

Un exemple intéressant de la théorie des nombres exprime un entier positif comme une somme de quatre carrés. Cela peut être fait relativement facilement en temps polynomial aléatoire (voir mon article de 1986 avec Rabin à https://dx.doi.org/10.1002%2Fcpa.3160390713 ), et si je me souviens bien, il y a maintenant même un temps polynomial déterministe Solution. Mais compter le nombre de telles représentations vous permettrait de calculer la fonction somme des diviseurs , qui est un temps polynomial aléatoire équivalent à la factorisation . Le problème de comptage est donc probablement difficile. $\sigma(n)$ $n$

Jeffrey Shallit
la source

"Donc, le problème de comptage est probablement difficile" vous voulez dire probablement

difficile? avez-vous des preuves?

# P

$\#P$

T ....

Par "probablement difficile", je veux dire qu'il s'agit d'un temps polynomial aléatoire équivalent à une factorisation entière.

Jeffrey Shallit

3

Donc, pour le rendre explicite: le problème n'est pas # P-dur (sauf si l'enfer se déchaîne).

Emil Jeřábek soutient Monica

@JeffreyShallit Y a-t-il un exemple

?

# P

$\#P$

T ...

Je pense que ce qui suit est un exemple encore plus simple: « Est-ce que

un bon plus diviseur que

» vs « Combien de diviseurs supérieur à

ne

ont? ». La version de décision est équivalente à "

est composite" donc c'est en

, mais la version de comptage ne semble pas plus facile que l'affacturage.

n

$n$

1

$1$

1

$1$

n

$n$

n

$n$

P

$P$

Dan Brumleve

17

Un exemple très agréable et simple de Graph Theory compte le nombre de circuits Eularian dans un graphe non orienté.

La version décision est facile (... et le problème des Sept Ponts de Königsberg n'a pas de solution :-)

La version de comptage est # P-hard: Graham R. Brightwell, Peter Winkler: Counting Eulerian Circuits est # P-Complete . ALENEX / ANALCO 2005: 259-262

Marzio De Biasi
la source

Cet article "Notre approche est de montrer que, à l'aide d'un oracle qui compte les circuits eulériens, une machine de Turing peut ... et" Nous souhaitons calculer le nombre d'orientations eulériennes de "Paragraphe-break" Nous construisons pour tout premier impair , un graphe dont le nombre d'orbes est équivalent à modulo . "Et" Nous répétons ce processus pour chaque premier p compris entre et , où , et ... "suggèrent certainement qu'ils ne donnent qu'une réduction parallèle, plutôt qu'une réduction de requête .

N

$N$

G

$G$

p

$p$

G_{p}

$G_p$

N

$N$

p

$p$

m

$m$

m^{2}

$m^2$

| E | = m

$|E| = m$

m^{ϵ}

$m^{\epsilon}$

@MarzioDeBiasi est la décision du circuit eulérien en NC?

T ....

1

@UN J. Il vous suffit de calculer la parité du degré de chaque nœud et de vérifier qu'ils sont tous égaux. Semble vraiment être en Caroline du Nord.

Sasho Nikolov

4

Vous pouvez prendre la parité de bits en utilisant une formule de taille ou un circuit de taille linéaire de profondeur . Donc, si votre graphique est donné comme une matrice d'adjacence, calculez la parité de chaque ligne, niez et prenez un ET. ET de bits peut être fait avec une formule de taille linéaire, donc globalement, vous obtenez une formule booléenne de taille et un circuit booléen de taille de profondeur (sur le ET-OU). Le problème est donc en fait dans .

n

$n$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$

n

$n$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$

{N C}^{1}

$\mathsf{NC}^1$

Sasho Nikolov

2

En fait, le problème se trouve dans .

{A C}^{0} [2]

$\mathrm{AC}^0[2]$

Emil Jeřábek soutient Monica

6

Concernant votre deuxième question, des problèmes tels que Monotone-2-SAT (décider de la satisfiabilité d'une formule CNF ayant au plus 2 littéraux positifs par clause) est totalement trivial (il suffit de vérifier si votre formule est vide ou non) mais le problème de comptage est # P-difficile. Il est même difficile d'approximer le nombre d'assignations satisfaisantes d'une telle formule (voir Sur la dureté du raisonnement approximatif, Dan Roth, Intelligence artificielle, 1996).

loup
la source

5

Extrait de [Kayal, CCC 2009] : Évaluation explicite des polynômes annihilants à un moment donné

Extrait du résumé: `` C'est le seul problème de calcul naturel où la détermination de l'existence d'un objet (le polynôme annihilant dans notre cas) peut être effectuée efficacement mais le calcul réel de l'objet est prouvablement difficile. ''

Let un champ et est un ensemble de -many degrés - polynômes -variate plus Un polynôme -annihilating est l'un quelconque (non trivial) r $\mathbb{F}$ $\vec{f} = (f_1, ..., f_k)\in\mathbb{F}[x_1, ..., x_n]$ $k$ $d$ $n$ $\mathbb{F}.$ $\vec{f}$ $A$ $A(f_1, ..., f_k) = 0.$

La décision est facile: sur tout terrain, et pour tous les polynômes - si il existe une telle annihilation pour . ((Via un argument de comptage de dimensions.)) $k$ $(f_1, ..., f_k)$ $k \ge n+1,$ $A$ $(f_1, ..., f_k)$

Le comptage est difficile: Définir annihilant-EVAL que le problème fonctionnel de l' évaluation d' un polynôme d'annihilation sur un point : Etant donné un premier et un ensemble qui ont annihilant unitaire minimal $p,$ $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ $A(0, ..., 0)\bmod{p}.$

ANNIHILATING-EVAL est -hard. De plus, le polynôme annihilant n'a pas une petite représentation de circuit à moins que s'effondre. $\#\mathsf{P}$ $A(t_1, ..., t_k)$ $\mathsf{PH}$

Daniel Apon
la source

1

Comme pour l'exemple de Marzio, la preuve de la revendication 15.2 de ce document semble indiquer qu'ils ne montrent de dureté que sous des réductions parallèles, plutôt que même sous des réductions de requête .

m^{ϵ}

$m^{\hspace{.02 in}\epsilon}$

1

Les ressources que je peux trouver semblent toutes en désaccord sur les définitions. Laissez AE être le problème dont traite votre réponse. (... suite)

1

(suite ...) Je ne l' ai pas essayé de travailler plus précisément ce que la classe de base qu'ils utilisent, mais serait très surpris si leur résultat était mieux que #P = DLOGTIME-uniform TC . (... suite)

(

$\big(\hspace{-0.07 in}$

^{0}

$^0$

)

$\hspace{-0.06 in}\big)$

^{| |}

$^{\hspace{-0.06 in}||\hspace{-0.06 in}}$

^{AE}

$^{\text{AE}}$

^{[\sqrt{n}]}

$^{\hspace{-0.05 in}[\sqrt{n}]}$

1

(suite ...) Pour autant que je peux voir, il ne pas suivre que LWPP MP poly .

\subseteq

$\subseteq$

^{AE}

$^{\text{AE}}$

^{[\sqrt[3]{n}]}

$^{[\sqrt[3]{n}]}$

/

$\hspace{-0.06 in}\big/\hspace{-0.04 in}$

1

Plus généralement, c'est-à-dire pour arbitraire (encore moins que ), la décision est facile à cause du critère jacobien, non? (Notez que le critère jacobien ne fonctionne que dans la caractéristique> ; dans la petite caractéristique positive, il y a un critère jacobien modifié en raison de Mittman-Saxena-Scheiblechner , mais cela ne mène apparemment qu'à un algorithme de décision ...)

k

$k$

n

$n$

m a x d e g f_{i}

$max deg f_i$

{N P}^{# P}

$\mathsf{NP}^{\mathsf{\# P}}$

Joshua Grochow

Problèmes faciles avec les versions de comptage dur

Réponses: