Est-ce difficile de compter le nombre de solutions?
Une question récente de Huck Bennett demandant si la classe PH était contenue dans la classe PP, a reçu des réponses quelque peu contradictoires (tout à fait vrai, semble-t-il). D'un côté, plusieurs résultats Oracle ont été donnés, et de l'autre Scott a suggéré que la réponse était probablement...
Certains problèmes de comptage impliquent de compter de manière exponentielle beaucoup de choses (par rapport à la taille de l'entrée), tout en ayant d'étonnants algorithmes déterministes exacts à temps polynomial. Les exemples comprennent: Comptage des correspondances parfaites dans un graphe...
Nous savons que le premier niveau de la hiérarchie polynomiale (c'est-à-dire NP et co-NP) est en PP, et que . Le théorème de Toda indique également que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Savons-nous si ? Si non, pourquoi est-ce que avec un oracle en est plus fort...
Étant donné un entier de longueur n bits, est-il difficile de produire le nombre de facteurs premiers (ou alternativement le nombre de facteurs) de N ?NNNnnnNNN Si nous connaissions la factorisation première de , ce serait facile. Cependant, si nous connaissions le nombre de facteurs premiers ou...
Soit un problème (de décision) dans NP et soit # sa version de comptage.XXXXXX Dans quelles conditions sait-on que "X est NP-complet" "#X est # P-complet"?⟹⟹\implies Bien sûr, l'existence d'une réduction parcimonieuse est une de ces conditions, mais c'est évident et la seule de ces conditions que...
Fixe un entier nnn et un alphabet Σ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\} . Définissez D FA ( n )DFA(n)DFA(n) comme la collection de tous les automates à états finis sur nnn états avec l'état de départ 1. Nous considérons tous les DFA (pas seulement ceux connectés, minimaux ou non dégénérés); ainsi |...
Supposons que nous relâchions le problème du comptage des colorations appropriées en comptant les colorations pondérées comme suit: chaque coloration appropriée obtient le poids 1 et chaque coloration incorrecte obtient le poids où est une constante et est le nombre d'arêtes dont les extrémités...
Quelles seraient les conséquences de #P = FP? Je m'intéresse aux conséquences pratiques et théoriques. D'un point de vue pratique, je m'intéresse particulièrement aux conséquences sur l'intelligence artificielle. Les pointeurs vers des articles ou des livres sont plus que bienvenus. Veuillez ne pas...
Étant donné un graphe non orienté et non pondéré et un entier pair , quelle est la complexité de calcul des ensembles de sommets tels que et le sous-graphe de restreint à l'ensemble des sommets admet une correspondance parfaite? La complexité # P-complète? Y a-t-il une référence pour ce problème?k...
Compter le nombre de correspondances parfaites dans un graphe bipartite est immédiatement réductible au calcul du permanent. Étant donné que trouver une correspondance parfaite dans un graphique non bipartite est dans NP, il existe une certaine réduction des graphiques non bipartites au permanent,...
Quelqu'un peut-il suggérer une bonne et récente enquête sur le comptage des problèmes et / ou des problèmes qui sont #P.
Supposons que nous ayons un problème paramétré par un paramètre de valeur réelle p qui soit "facile" à résoudre lorsque et "difficile" lorsque p = p 1 pour certaines valeurs p 0 , p 1 .p = p0p=p0p=p_0p = p1p=p1p=p_1p0p0p_0p1p1p_1 Un exemple est le comptage des configurations de spin sur les...
Rappelons le nombre de nombres premiers est la fonction de décompte des nombres premiers . Par "PRIMES in P", le calcul est en #P. Le problème # P-est-il complet? Ou, peut-être, il y a une raison complexe de croire que ce problème n'est pas # P-complet? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n)...
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 à 222 -SAT et le nombre de tri topologiques. Existe-t-il d'autres classes...
Laissez un entier fonction d'une valeur telle que 2 F est en # P . S'ensuit-il que F est en # P ? Y a-t-il des raisons de croire qu'il est peu probable que cela tienne toujours? Des références que je devrais connaître?FFF2F2F2F#P#P\#PFFF#P#P\#P De façon assez surprenante, cette situation est...
Soit le nombre d'arbres couvrant un graphe à sommets. Il existe un algorithme qui calcule dans les opérations arithmétiques . Cet algorithme consiste à calculer , où Q est le laplacien de G et J est la matrice constituée uniquement de 1 . Pour plus d'informations sur cet algorithme, voir Biggs -...
Des travaux ont-ils été effectués sur la façon dont la complexité des instances aléatoires de # 2-SAT varie avec la densité de la clause? C'est-à-dire: comment la difficulté de compter des solutions satisfaisantes pour une instance générée aléatoirement de 2-SAT varie-t-elle, comme la densité de...
Comment puis-je déterminer le nombre de chemins simples uniques dans un graphique non orienté? Soit pour une certaine longueur, soit pour une plage de longueurs acceptables. Rappelez-vous qu'un chemin simple est un chemin sans cycle, je parle donc de compter le nombre de chemins sans...
Version courte. La preuve originale que # 2-SAT est #P -complete montre, en fait, que les instances de # 2-SAT qui sont à la fois monotones (n'impliquant la négation d'aucune variable) et bipartites (le graphique formé par les clauses sur le est un graphe bipartite) sont #P -hard. Ainsi, les deux...
On m'a dit qu'il existe de bons algorithmes de temps polynomiaux pour approximer le nombre de chemins simples dans un graphe orienté d'un sommet de départ donné à un sommet de fin donné t . Quelqu'un connaît-il une bonne référence à ce sujet?sssttt Contexte: compter le nombre exact de chemins dans...