Je voudrais connaître l'état actuel de la transition de phase pour les k-sat aléatoires, étant donné n variables et m clauses, quel est le c = m / n le mieux connu pour les bornes supérieures et
À la SODA 2006, l'article de Martin Grohe et D niel Marx "Résolution des contraintes via des couvertures de bords fractionnaires" ( citation ACM ) a montré que pour la classe des hypergraphes H avec une largeur d'hypertree fractionnée bornée, CSP ( H ) \ in PTIME .a´a´\acute{\rm...
Graphique automorphismes est une permutation de noeuds du graphe qui induit une bijection sur l'ensemble d'arêtes . Formellement, c'est une permutation de nœuds tels que ssiEEEfff(u,v)∈E(u,v)∈E(u,v)\in E(f(u),f(v))∈E(f(u),f(v))∈E(f(u),f(v))\in E Définissez un bord violé pour une permutation comme...
Cette question s'est posée dans mon esprit après avoir lu les contributions d'András Salamon et Colin McQuillan à ma question précédente Compter les solutions des formules Monotone-2CNF . EDIT 30 e mars 2011 question n ° 2. Ajouté EDIT 29 e octobre 2010 Question reformulée après proposition András...
Hiroimono est un puzzle populaire complet. Je m'intéresse à la complexité informatique d'un puzzle connexe.NPNPNP Le problème est: Entrée : étant donné un ensemble de points sur une grille carrée x et un entiern knnnnnnkkk Question : Existe-t-il un polygone rectiligne (ses côtés parallèles à l' axe...
Soit une permutation. Notez que tandis que agit sur un domaine infini, sa description peut être finie. Par description , je veux dire un programme qui décrit les fonctionnalités de . (Comme dans la complexité de Kolmogorov.) Voir les explications ci-dessous. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi...
Quelqu'un connaît-il un ensemble de problèmes qui varient uniformément et qui couvrent l'une des hiérarchies "intéressantes" de complexité et de calculabilité? Par intéressant, je veux dire, par exemple, la hiérarchie polynomiale, la hiérarchie arithmétique ou la hiérarchie analytique. Ou peut-être...
La résolution est un schéma pour prouver l'insatisfiabilité des CNF. Une preuve en résolution est une déduction logique de la clause vide pour les clauses initiales du CNF. En particulier, toute clause initiale peut être déduite, et de deux clauses A∨xA∨xA \lor x et la clause peut également être...
Contexte La complexité du circuit est définie comme l'ensemble des familles de circuits (c'est-à-dire des séquences de circuits, une pour chaque taille d'entrée) de profondeur bornée et de taille polynomiale construites à l'aide de fan-in illimités ET, OU et NON.AC0AC0AC^0 La fonction de parité...
Dans une question précédente sur la hiérarchie temporelle, j'ai appris que les égalités entre deux classes peuvent être propagées à des classes plus complexes et les inégalités peuvent être propagées à des classes moins complexes, avec des arguments utilisant le remplissage. Par conséquent, une...
Dans cette question , il a été mentionné qu'il existe des versions de complexité descriptive du théorème de Rice. J'ai trouvé une preuve du théorème suivant: Étant donné une classe de complexité C , les propriétés non triviales des langages en C ne peuvent pas être calculées en C J'avais déjà posté...
Énoncé du problème: Soit un automate de refoulement (potentiellement non déterministe) et soit son alphabet d'entrée. Y a-t-il un mot st accepté par ?A w ∈ A ∗ | w | ≤ k MMMMAA\cal Aw∈A∗w∈A∗w \in \cal A^*|w|≤k|w|≤k|w| \leq kMMM Ce problème est-il NP-complet? At-il été étudié? Existe-t-il un...
Étant donné un circuit booléen sur variables (qui utilise uniquement les portes NON, ET et OU), quelle est la manière la plus efficace d'extraire la formule booléenne représentée par le circuit? Existe-t-il un algorithme de polytime pour ce
Existe-t-il un moyen pour un prouveur de convaincre un vérificateur qu'une expression HORN-SAT est satisfaisable? Bien sûr, cela peut sembler idiot, car il existe des algorithmes de temps linéaires pour HORN-SAT. D'un autre côté, HORN-SAT est P-complet, ce qui signifie qu'il n'a pas d'algorithmes...
Je jouais avec la question très intéressante et toujours ouverte " Alphabet of single-tape Turing machine " (par Emanuele Viola) et j'ai trouvé la langue suivante: L = { x ∈ { 0 , 1 }n st | x | = n = 2m et c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1
En un mot, les théorèmes de la hiérarchie du temps disent qu'une machine de Turing peut résoudre plus de problèmes si elle a plus de temps pour le calcul. En détail pour TM déterministe et fonctions constructibles dans le temps avec c'est et pour TM non déterministe et fonctions constructibles dans...
Un programme span est une manière linéaire-algébrique de spécifier une fonction booléenne présentée ici . Récemment, ce modèle a été utilisé pour montrer que la méthode de l'adversaire négatif fournit une caractérisation étroite (au moins jusqu'à ) de la complexité des requêtes quantiques.Journaln...
Considérez le problème de l'ensemble dominant dans les graphiques généraux, et soit le nombre de sommets dans un graphique. Un algorithme d'approximation gourmand donne une garantie d'approximation du facteur 1 + log n , c'est-à-dire qu'il est possible de trouver en temps polynomial une solution S...
Bien que les séparations exponentielles entre la complexité des requêtes quantiques à erreurs limitées ( ) et la complexité des requêtes déterministes ( D ( f ) ) ou la complexité des requêtes randomisées à erreurs limitées ( R ( f ) ) soient connues, elles ne s'appliquent qu'à certaines fonctions...
Mise à jour: Il semble que ce problème ait été étudié et résolu récemment, voir cet article wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton Et aussi cette enquête: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Supposons qu'au lieu de l'ensemble habituel de mots, {0,1} *, nos mots...