Existe-t-il des problèmes naturels dans qui ne sont pas (connus pour être / pensés être) dans ?U P ∩ c o U PNP∩coNPNP∩coNPNP \cap coNPUP∩coUPUP∩coUPUP \cap coUP Évidemment, le grand que tout le monde connaît dans est la version décisionnelle de l'affacturage (n'a pas un facteur de taille au plus...
Il est bien connu que la connectivité st dirigée est complète en . Résultat percée Reingold a montré que undirected st-connectivité est en . La connectivité st dirigée planaire est connue pour être dans . Cho et Huynh ont défini un problème de sac à dos paramétré et ont présenté une hiérarchie de...
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...
Le problème suivant est-il NP-difficile? Étant donné une configuration de carte pour brouillons internationaux , trouvez un mouvement juridique unique.n×nn×nn\times n Le problème correspondant pour les vérificateurs américains (ou versions anglaises) est trivialement résoluble en temps polynomial....
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...
Je ne peux pas penser à un tel modèle, peut-être une forme de calcul lambda typé? un automate cellulaire élémentaire? Cela réfuterait presque le «principe d'équivalence informatique» de Wolfram: Presque tous les processus qui ne sont évidemment pas simples peuvent être considérés comme des calculs...
Une machine PHPHPH accès oracle à une fonction booléenne aléatoire f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} , et deux spectres de Fourier ggg et hhh . Le spectre de Fourier d'une fonction fff est défini comme F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R :...
Pour une formule 3CNF laisser soit le nombre de maximal de clauses satisfaites dans toute affectation à . On sait que Max-3SAT est difficile à estimer (sous réserve de P ≠ NP), c'est-à-dire qu'il n'y a pas d'algorithme de polytime dont l'entrée est une formule 3CNF , et dont la sortie est le nombre...
Connaissez-vous un wiki à jour dédié aux problèmes d'optimisation NP avec leur meilleur résultat d'approximation et de dureté? Sur la base des commentaires, il semble qu'il est prudent de supposer qu'il n'y a pas une telle ressource (voir la fin de cette question pour deux options proches). -...
Cette question a été migrée à partir de Stack Overflow car il est possible d'y répondre sur Théorical Computer Science Stack Exchange. Migré il y a 8 ans . Étant donné que la correspondance Curry-Howard est si largement diffusée / étendue, y a-t-il une différence entre les preuves et les...
Existe-t-il quelque chose de connu sur la classe des graphes avec la propriété que tous les ensembles indépendants maximaux ont la même cardinalité et sont donc des IS maximum? Par exemple, prenez un ensemble de points dans le plan et considérez le graphique des intersections entre tous les...
Ceci est ma première question sur la pile cstheory, alors ne soyez pas trop impoli si je viole l'étiquette d'une manière ou d'une autre) Comme nous le savons, en mathématiques, même des mathématiciens, des superstars et des génies célèbres font de temps en temps de graves erreurs. Par exemple, le...
Sur quels sujets TCS manquants sur Wikipédia aimeriez-vous le plus avoir un article? Il peut s'agir d'omissions flagrantes ou simplement de sujets qui, selon vous, devraient vraiment avoir un article. Un sujet par réponse s'il vous plaît afin que les plus recherchés puissent être votés. Mise à jour...
Étant donné une langue régulière (NFA, DFA, grammaire ou expression régulière), comment peut-on compter le nombre de mots acceptés dans une langue donnée? "Avec exactement n lettres" et "avec au plus n lettres" présentent un intérêt. Margareta Ackerman a deux articles sur le sujet connexe de...
Shiva Kintali vient d'annoncer un résultat (cool!) Que l' isomorphisme des graphes pour les graphes à largeur d'arbre bornée de largeur est ⊕ L -hard≥4≥4\geq 4⊕L⊕L\oplus L . De manière informelle, ma question est: "C'est difficile?" Nous savons que non uniformément , voir les réponses à cette...
L'étude de la représentation succincte des graphiques a été lancée par Galperin et Wigderson dans un article de 1983, où ils prouvent que pour de nombreux problèmes simples comme la recherche d'un triangle dans un graphique, la version succincte correspondante dans -complete. Papadimitriou et...
Je ne suis pas un théoricien de l'informatique, mais je pense que ce problème du monde réel appartient ici. Le problème Mon entreprise possède plusieurs unités à travers le pays. Nous avons offert aux employés la possibilité de travailler sur une autre unité. Mais il y a une condition: le nombre...
Je suis sûr que tout le monde connaît l' expérience de Buffon sur l'aiguille au XVIIIe siècle, qui est l'un des premiers algorithmes probabilistes à calculer .ππ\pi L'implémentation de l'algorithme dans les ordinateurs nécessite généralement l'utilisation de , ou d'une fonction trigonométrique,...
On dirait que George Gonthier et ses collaborateurs ont fini de formaliser le théorème des ordres impairs . Dans ses travaux antérieurs sur le théorème des quatre couleurs, Gonthier a inventé un tas de nouveaux algorithmes (principalement des variantes de BDD et d'algorithmes graphiques) qui se...
Soit une matrice entière carrée, et soit un entier positif. Je m'intéresse à la complexité du problème de décision suivant:MMMnnn L'entrée en haut à droite de positive?MnMnM^n Notez que l'approche évidente du quadrillage itéré (ou de tout autre calcul explicite) nous oblige à gérer potentiellement...