Une réduction est la transformation d'un problème en un autre problème. Un exemple d'utilisation d'une réduction serait de montrer si un problème P est indécidable. Ceci serait réalisé en transformant ou en effectuant une réduction d'un problème de décision P P en un problème indécidable. Si cela peut être réalisé, nous avons montré que ce problème P est indécidable.
Pourquoi la plupart des gens préfèrent-ils utiliser plusieurs réductions pour définir l'exhaustivité des NP au lieu, par exemple, des réductions de
Le problème de la somme des racines carrées pose, étant donné deux séquences a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n et b1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n d’entiers positifs, si la somme inférieure à, égale à to, ou supérieure à la somme . Le statut de complexité de ce problème est ouvert;...
On suppose que le caractère aléatoire n’étend pas la puissance des algorithmes de temps polynomiaux, c’est-à-dire que est supposé tenir. D'autre part, le hasard semble avoir un effet assez différent sur les réductions de temps polynomiales . Selon le résultat bien connu de Valiant et Vazirani, la...
Le théorème de Valiant-Vazirani dit que s'il existe un algorithme polynomial de temps (déterministe ou aléatoire) pour distinguer entre une formule SAT qui a exactement une affectation satisfaisante et une formule insatisfaisante - alors NP = RP . Ce théorème est prouvé en montrant que UNIQUE-SAT...
Le blog de Scott Aaronson a donné aujourd'hui une liste de problèmes / tâches ouverts intéressants en complexité. Un en particulier a retenu mon attention: Construisez une bibliothèque publique d'instances 3SAT, avec aussi peu de variables et de clauses que possible, qui aurait des conséquences...
Y a-t-il un exemple de langue qui est en NPNPNP , mais où nous ne pouvons pas prouver ce fait directement en montrant qu'il existe un témoin polynomial d'appartenance à cette langue? Au lieu de cela, le fait que la langue est en NPNPNP serait prouvé en la réduisant à une autre langue en NPNPNP , où...
Certains problèmes NP-durs qui sont exponentiels sur les graphes généraux sont sous-exponentiels sur les graphes planaires car la largeur de l'arborescence est au maximum de et ils sont exponentiels dans la largeur de l'arborescence.4.9|V(G)|−−−−−−√4.9|V(G)|4.9 \sqrt{|V(G)|} Fondamentalement, je...
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,...
Il y a clairement une réduction de CLIQUE à k-Color car ils sont tous deux NP-Complete. En fait, je peux en construire un en composant une réduction de CLIQUE à 3-SAT avec une réduction de 3-SAT à k-Color. Je me demande s'il y a une réduction directe raisonnable entre ces problèmes. Disons, une...
Certains d'entre vous ont peut-être suivi cette question , qui a été fermée en raison d'un niveau de recherche insuffisant. J'extrais donc la partie de la question qui se situe au niveau de la recherche. Au-delà des techniques "plus simples", telles que la réduction au tri ou un problème...
C'est dans la ligne des " Algorithmes du livre ". Bien que les réductions soient également des algorithmes, je pensais qu'il était douteux que l'on pense à une réduction en réponse à la question sur les algorithmes du livre. D'où une requête distincte! Les réductions de toutes sortes sont les...
Cette question concerne la relation entre la multiplication normale des nombres binaires et la multiplication polynomiale mod 2. Pour rendre la question concrète, j'aimerais idéalement savoir s'il existe une meilleure solution à la question de Knuth vol. 2, 3e édition, page 420 que celle donnée...
Dans l'article "LA COMPLEXITÉ DES PROBLÈMES DE SATISFACABILITÉ" de Thomas J. Schaefer, l'auteur a mentionné que This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the...
Dans cette question , nous semblons avoir identifié un problème naturel qui est NP-complet sous des réductions aléatoires, mais peut-être pas sous des réductions déterministes (bien que cela dépende des hypothèses non prouvées dans la théorie des nombres qui sont vraies). Existe-t-il d'autres...
USTCONN est le problème qui nécessite de décider s'il existe un chemin entre le sommet source et le sommet cible t dans un graphique G , où ils sont tous donnés dans le cadre de l'entrée.ssstttGGG Omer Reingold a montré que USTCONN est en L (doi: 10.1145 / 1391289.1391291 ). La preuve construit un...
Ici, l'objectif est de réduire un problème SAT arbitraire à 3-SAT en temps polynomial en utilisant le moins de clauses et de variables. Ma question est motivée par la curiosité. Moins formellement, j'aimerais savoir: "Quelle est la réduction" la plus naturelle "du SAT au 3-SAT?" Maintenant, la...
J'ai récemment lu une preuve qui avait pour but de montrer qu'un problème était fortement NP-difficile, simplement en le réduisant (en temps polynomial) à partir d'un problème fortement NP-difficile. Cela n'avait aucun sens pour moi. J'aurais pensé que vous deviez montrer que tous les nombres...
Il est connu que l'intersection de trois matroïdes généraux est NP-difficile ( source ), ce qui se fait par réduction du cycle hamiltonien. La réduction utilise un matroïde graphique et deux matroïdes de connectivité. Un cas particulier d'un problème sur lequel je travaille peut être résolu par...
Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction...
J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile. Somme Sous - ensemble: Étant donné X= { x1, . . . , xn}X={X1,...,Xn}X = \{x_1,...,x_n\}...