On sait que le cycle hamiltonien (jambon en abrégé) est NP-complet et que le cycle planaire du jambon est NP-complet. La preuve pour Planar Ham Cycle n'est pas de Ham Cycle. Existe-t-il un joli gadget qui, étant donné un graphe G, remplacera tous les croisements par un gadget plan afin que vous...
Motivé par le commentaire de Fortnow sur mon article, Preuve que le problème d'isomorphisme graphique n'est pas completNPNPNP G I N P N P P G I P , et par le fait que est un candidat principal pour le problème intermédiaire (pas complet ni en ), je suis intéressé par des preuves connues que se...
Dans l'enquête "Small Depth Quantum Circuits" de D. Bera, F. Green et S. Homer (p. 36 de ACM SIGACT News, juin 2007 vol. 38, no. 2) , j'ai lu la phrase suivante: La version classique de (dans laquelle les portes et ont un fanout au plus constant) est manifestement plus faible que . A N D O R A C 0Q...
La théorie de la complexité, à travers des concepts tels que la complétude NP, fait la distinction entre les problèmes de calcul qui ont des solutions relativement efficaces et ceux qui sont insolubles. La complexité "fine" vise à affiner cette distinction qualitative en un guide quantitatif quant...
L'accès à un oracle fournirait une accélération super-polynomiale majeure pour tout dans N P - P (en supposant que l'ensemble n'est pas vide). Il est cependant moins clair combien P bénéficierait de cet accès Oracle. Bien sûr, l'accélération dans P ne peut pas être super-polynomiale, mais elle peut...
Le problème Not All Equal -SAT (NAE k -SAT), étant donné un ensemble C de clauses sur un ensemble X de variables booléennes telles que chaque clause contient au plus k littéraux, demande s'il existe une affectation de vérité des variables telles que chaque clause contient au moins un vrai et au...
J'essaie actuellement de trouver des problèmes EXPSPACE-complets (principalement pour trouver l'inspiration pour une réduction), et je suis surpris par le petit nombre de résultats à venir. Jusqu'à présent, je les ai trouvés et j'ai du mal à élargir la liste: universalité (ou autres propriétés) des...
Un polynôme est une projection monotone d'un polynôme g ( y 1 , … , y m ) si m = poly ( n ) , et il y a une affectation π : { y 1 , … , y m } → { x 1 , … , x n , 0 ,f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n)g(y1,…,ym)g(y1,…,ym)g(y_1,\ldots,y_m)mmm(n)(n)(n) tel que f ( x 1 , … , x n ) = g ( π ( y 1 ) , …...
Je fixe un langage régulier sur un alphabet , et je considère le problème suivant que j'appelle la planification de la lettre pour . De manière informelle, l'entrée me donne lettres et un intervalle pour chaque lettre (c'est-à-dire une position minimale et maximale), et mon objectif est de placer...
Récemment, j'ai vu plusieurs articles sur arxiv qui se réfèrent à un système de preuve appelé somme des carrés. Quelqu'un peut-il expliquer ce qu'est une preuve de somme des carrés et pourquoi ces preuves sont importantes / intéressantes? Comment sont-ils liés à d'autres systèmes de preuve...
Le théorème original de la hiérarchie temporelle non déterministe est dû à Cook (le lien est à S. Cook, Une hiérarchie pour la complexité temporelle non déterministe , JCSS 7 343–353, 1973). Le théorème stipule que pour tout nombre réel et , si alors NTIME ( ) est strictement contenu dans NTIME (...
Je lisais " Est-ce que P par rapport à NP est officiellement indépendant? ", Mais je suis resté perplexe. Il est largement admis dans la théorie de la complexité que . Ma question est de savoir si ce n'est pas prouvable (disons dans ). (Supposons que nous découvrions seulement que est indépendant...
En lisant une réponse de Peter Shor et une question précédente d'Adam Crume, j'ai réalisé que j'avais des idées fausses sur ce que signifie être -hard.PP\mathsf{P} Un problème est -hard si un problème dans est réductible à lui avec des réductions (ou si vous préférez ). Un problème est en dehors de...
Je me demandais quels papiers je devrais lire pour comprendre cette question Une connexion inattendue à d'autres domaines des mathématiques tels que la géométrie algébrique ou la cohomologie supérieure. Peut-être même un domaine des mathématiques pas encore développé. Peut-être que quelqu'un...
De nombreux problèmes de graphes algorithmiques peuvent être résolus en temps polynomial à la fois sur des graphes non pondérés et pondérés. Quelques exemples: chemin le plus court, arbre couvrant minimum, chemin le plus long (dans les graphiques acycliques dirigés), débit maximal, coupe minimale,...
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...
Cette question fait suite à la question sur les algorithmes d'ADN posée par Aadita Mehra . Dans ses commentaires, Joe Fitzsimmons a déclaré, en partie: [L] e rayon du système doit évoluer proportionnellement à la masse pour éviter cela. La puissance de calcul évolue au plus linéairement dans la...
Dans La complexité de calcul de l'optique linéaire ( ECCC TR10-170 ), Scott Aaronson et Alex Arkhipov soutiennent que si les ordinateurs quantiques peuvent être efficacement simulés par des ordinateurs classiques, la hiérarchie polynomiale s'effondre au troisième niveau. Le problème motivant est...
Dans les tests de propriétés de graphe, un algorithme interroge un graphe cible pour la présence ou l'absence d'arêtes et doit déterminer si la cible a une certaine propriété ou est ϵϵ\epsilon loin d'avoir la propriété. (Un algorithme peut être demandé pour réussir avec une face ou deux faces d'...
Afin de vérifier ma compréhension, je voudrais partager quelques réflexions sur les besoins énergétiques du calcul. Ceci fait suite à ma question précédente et pourrait être lié à la question de Vinay sur les lois de conservation . Il m'est apparu que, d'un point de vue thermodynamique, l'exécution...