On ne sait pas si isomorphisme de graphes (IG) pour les graphiques fortement réguliers (SRGS) est en P . Y a-t-il des indices qu'il pourrait ou non être GI- Complet? Y a-t-il des conséquences importantes dans de tels cas? (Similaire à la croyance que l'IG peut ne pas être
Soit la complexité de Kolmogorov d'une chaîne x . Existe-t-il une chaîne telle que K ( x x ) < K ( x ) . (Ici x x est la concaténation de x avec lui-même). Une question similaire mais différente a été posée ici , mais le contre-exemple donné dans la réponse à cette question ne fonctionne pas...
Le théorème de Savitch montre que pour toutes les fonctions suffisamment grandes f , et prouver que cela est serré est un problème ouvert depuis des décennies .N S P A C E (f( n ) ) ⊆ D S P A C E ( f( n )2)NSPUNECE(F(n))⊆réSPUNECE(F(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)FFf...
Il n'y a que très peu d'informations que je peux trouver sur le problème NP-complet de la résolution de l'équation diophantienne linéaire en nombres entiers non négatifs. C'est - à - dire, est - il une solution non négatif à l'équation a 1 x 1 + a 2 x 2 + . . . + a n x n = b , où toutes les...
Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord...
Nous savons (pour le moment environ 40 ans, merci Adleman, Bennet et Gill) que l'inclusion BPP P / poly, et un BPP / poly P / poly encore plus fort . Le "/ poly" signifie que nous travaillons de manière non uniforme (un circuit séparé pour chaque longueur d'entrée ), tandis que P sans ce "/ poly"...
L'analyse du pire et du cas moyen sont des mesures bien connues de la complexité d'un algorithme. L'analyse lissée récemment est apparue comme un autre paradigme pour expliquer pourquoi certains algorithmes exponentiels dans le pire des cas fonctionnent si bien dans la pratique, par exemple...
Le problème suivant est-il dans PTIME ou coNP-hard: Étant donné deux expressions booléennes et e 2 dans les variables x 1 , … , x n , sans négation (c'est-à-dire que les expressions sont entièrement construites via ∧ et ∨ ). Décidez si e 1 ≡ e 2 , c'est-à-dire qu'ils ont la même valeur pour toutes...
Contexte Un arbre de décision binaire TTT est un arbre enraciné où chaque nœud interne (et racine) est étiqueté par un index sorte qu'aucun chemin de la racine à la feuille ne répète un index, les feuilles sont étiquetés par des sorties dans , et chaque bord est étiqueté par pour l'enfant gauche et...
Le problème suivant apparaît dans la liste d'Aaronson Dix demi-grands défis pour la théorie de l'informatique quantique . Est-ce que BQP=BPPBQNCBQP=BPPBQNC\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} En d'autres termes, la partie "quantique" de n'importe quel algorithme quantique peut-elle être...
Soit un digraphe (pas nécessairement un DAG) et soit s , t ∈ V ( G ) . Quelle est la complexité de compter le nombre de simples s - t chemins dans G . ggGs , t ∈ V( G )s,t∈V(g)s,t \in V(G) s - ts-ts-tggG Je m'attendrais à ce que le problème soit # -complet, mais je n'ai pas pu trouver une référence...
Quel est le nombre minimal de portes binaires nécessaires pour calculer ET et OU de bits d'entrée simultanément? La borne supérieure triviale est . Je pense que c'est optimal, mais comment le prouver? La technique d'élimination de porte standard ne fonctionne pas ici car en attribuant une constante...
Dans nos travaux récents, nous résolvons un problème de calcul qui s'est posé dans un contexte combinatoire, en supposant que , où ⊕EXP≠⊕EXPEXP≠⊕EXP\mathsf{EXP} \ne \mathsf{\oplus{}EXP} est la version E X P de ⊕⊕EXP⊕EXP\mathsf{\oplus{}EXP}EXPEXP\mathsf{EXP} . Le seul papier sur...
Quand on nous donne une décomposition arborescente d'un graphe de largeur , il y a plusieurs façons de le rendre "agréable". En particulier, il est connu qu'il est possible de le transformer en une décomposition d'arbre où l'arbre est binaire et sa hauteur est . Ceci peut être réalisé tout en...
Supposons que l'on nous donne un ensemble de n variables booléennes x_1, ..., x_n et un ensemble de m fonctions y_1 ... y_m où chaque y_i est le XOR d'un sous-ensemble (donné) de ces variables. Le but est de calculer le nombre minimum d'opérations XOR que vous devez effectuer pour calculer toutes...
Cette question peut être posée soit dans le cadre de la complexité des circuits des circuits booléens, soit dans le cadre de la théorie de la complexité algébrique, soit probablement dans de nombreux autres contextes. Il est facile de montrer, en comptant les arguments, qu'il existe des fonctions...
Existe-t-il un algorithme de réarrangement temporel sur place linéaire? C'est l'algorithme que certaines mains particulièrement habiles sont capables d'exécuter: diviser uniformément un tableau d'entrée de taille égale, puis entrelacer les éléments des deux moitiés. Mathworld a une brève page sur...
La complexité de l'information a été un outil très utile dans la complexité de la communication, principalement utilisée pour réduire la complexité de la communication des problèmes distribués. Existe-t-il un analogue de la complexité des informations pour la complexité des requêtes? Il existe de...
Nous savons que les solveurs SAT basés sur DPLL ne répondent pas correctement aux cas insatisfaisants de (principe du pigeon), par exemple sur "il y a une cartographie injective de n + 1 à n ":PHPPHP\mathrm{PHP}n+1n+1n+1nnn
Étant donné une matrice (en supposant ), quel est l'algorithme le plus rapide pour calculer son rang et sa base des colonnes?m × nm×nm \times nm ≥ nm≥nm \ge n Je suis conscient qu'il peut être résolu par intersection matroïde linéaire, ce qui implique un algorithme déterministe temporel et un...