Existe-t-il une séquence de graphes non dirigés , où chaque a exactement sommets et le problème{ Cn}n ∈ N{Cn}n∈N\{C_n\}_{n\in \mathbb N}CnCnC_nnnn Étant donné et un graphe , est-il un sous-graphe induit de ?G C n GnnnggGCnCnC_nggG est connu pour être dans la classe ? (Par exemple, lorsque , c'est...
La célèbre conjecture d'isomorphisme de Berman et Hartmanis dit que tous langages complets sont isomorphes en temps polynomiaux (p-isomorphes) les uns aux autres. La signification clé de la conjecture est qu'elle implique . Il a été publié en 1977, et une preuve à l'appui était que tous problèmes...
Le problème d'arrêt des machines Turing est peut-être l'ensemble canonique indécidable. Néanmoins, nous prouvons qu'il existe un algorithme qui en décide presque toutes les instances. Le problème de l'arrêt fait donc partie de la collection croissante de ceux qui présentent le phénomène de «trou...
Je m'intéresse au problème suivant: étant donné une matrice , y a-t-il un graphe non orienté sur n sommets dont la matrice d'adjacence au carré est cette matrice?n × nn×nn\times nnnn La complexité de calcul de ce problème est-elle connue? Remarques: Bien sûr, cela peut aussi être formulé comme un...
Dans la description officielle du problème de Clay pour P versus NP, il est indiqué que découlerait de la démonstration que "chaque langue de E [la classe de langues reconnaissable en temps exponentiel avec une machine de Turing déterministe] peut être calculée par une famille de circuits booléens....
Je suis intéressé à apprendre les connexions entre le «chaos» ou, plus largement, les systèmes dynamiques et la question . Voici un exemple du type de littérature que je recherche:P=NPP=NPP{=}NP Ercsey-Ravasz, Mária et Zoltán Toroczkai. "La dureté d'optimisation comme chaos transitoire dans une...
Existe-t-il des problèmes NP complets sans sous-ensemble infini d'instances telles que l'appartenance à peut être décidée en temps polynomial, et pour tout , peut être résolu en temps polynomial? (En supposant )ΦΦ\PhiΦΦ\Phix∈Φx∈Φx \in \PhixxxP≠NPP≠NPP \neq
Existe-t-il un projet en cours pour vérifier formellement les théorèmes et les preuves de la théorie de la complexité à l'aide d'un assistant de preuve comme Coq? Y a-t-il des limites à
Supposons que l'on vous donne un graphe H. connecté, simple et non orienté Le problème de coupe sans H est défini comme suit: Étant donné un graphe simple et non orienté G, existe-t-il une coupure (partition des sommets en deux ensembles non vides, L, R) de sorte que les graphes induits par les...
En règle générale, les algorithmes efficaces ont un runtime polynomial et un espace de solution exponentiellement grand. Cela signifie que le problème doit être facile dans deux sens: premièrement, le problème peut être résolu en un nombre polynomial d'étapes, et deuxièmement, l'espace de la...
Il est bien connu que l'ensemble des langages ayant des systèmes de preuve interactifs à deux prouveurs, dans lesquels le vérificateur s'exécute en temps polynomial (MIP), est NEXP. Mais existe-t-il des limites connues sur la puissance de ces preuves interactives lorsque les prouveurs sont limités...
Dans le "dernier paragraphe" de la "première page" de l'article suivant: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , «If NP Has Polynomial-Size Circuits, then MA = AM», Theoretical Computer Science, 1995. J'ai rencontré une affirmation quelque peu contre-intuitive:...
J'ai trouvé le livre Pairwise Independence and Derandomization sur le sujet, mais il est plus axé sur la recherche que sur le tutoriel. Je suis nouveau sur le sujet de la "dérandomisation", et en tant que tel, je voulais savoir de quelle référence commencer? Je préfère celui qui traite de la...
Soit 0 ≤ p ≤ 10≤p≤10\le p\le 1 et considérons le problème de décision CLIQUE p entrée: nombre entier s , graphe G avec t sommets et bords Question: ne contient une clique sur au moins les sommets?pp_p sssggGttt⌈ p ( t2) ⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil ggGsss Une instance de CLIQUE contient une...
Une distribution est dit ε -fool une fonction f si | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Et on dit qu'il trompe une classe de fonctions s'il trompe chaque fonction de cette classe. Il est connu que les espaces biaisés ϵ trompent la classe de parités sur les sous-ensembles. (voir...
Pour autant que je sache, toutes les règles de pivot déterministes connues pour les algorithmes simplex ont des entrées spécifiques sur lesquelles l'algorithme nécessite un temps exponentiel (ou du moins pas polynomial) pour trouver l'optimum. Appelons ces instances «pathologiques» car généralement...
Il est facile de voir que tout problème décidable dans un espace de log déterministe ( ) s'exécute au plus en temps polynomial ( ). De nombreux algorithmes connus de l'espace de journalisation (par exemple: connectivité st non dirigée, isomorphisme de graphe planaire) s'exécutent dans où est...
Je cherche à savoir s'il y a des résultats généraux ou des exemples concernant l'exhaustivité NP du problème de trouver une deuxième solution à un problème NP-complet. Plus précisément, je suis intéressé par tout problème de la forme suivante: Étant donné une solution à une instance d'un problème...
J'ai essayé de lire « Perles de conception d'algorithmes fonctionnels », puis « L'algèbre de programmation », et il existe une correspondance évidente entre les types de données définis de manière récursive (et polynomiale) et les objets combinatoires, ayant la même définition récursive et menant...
Comme cela est bien connu, la PARITÉ ne peut pas être effectuée dans des circuits de profondeur constante de taille poly, et en fait, les circuits const-dept nécessitent un nombre de portes EXP. Qu'en est-il des circuits QUANTUM? a) La PARITE peut-elle être effectuée avec un circuit quantique qui a...