Il y a eu quelques efforts pour attaquer le problème d'isomorphisme des graphes en utilisant la marche aléatoire quantique des bosons à noyau dur (symétrique mais sans double occupation). La puissance symétrique de la matrice d'adjacence, qui semblait prometteuse, s'est révélée incomplète pour les...
Il est formulé en étendant les graphiques de seuil . Étant donné un graphique de seuil où C est la clique et I est l'ensemble indépendant, mon extension est la suivante: Chaque sommet v ∈ I peut être remplacé par une nouvelle clique K v de telle sorte que les sommets de K v aient le mêmes voisins...
ETH déclare que SAT ne peut pas être résolu dans le pire des cas en temps sous-exponentiel. Et le cas moyen? Y a-t-il des problèmes naturels dans le NP qui sont supposés être exponentiellement durs dans le cas moyen? Par cas moyen, on entend le temps de fonctionnement moyen avec une distribution...
Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné parXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk= Ak∪ Bk∪ Mk où UNEk= { aje∣ 1 ≤ i ≤ k...
Fixer un problème de recherche NP-complet, par exemple le formulaire de recherche de SAT. La recherche de Levin fournit un algorithme L pour résoudre X qui est optimal dans un certain sens. Plus précisément, l'algorithme est "Exécute tous les programmes P possibles en queue d'aronde sur l'entrée x...
Considérons un prédicat monotone sur l'ensemble de puissance (ordonné par inclusion). Par "monotone" je veux dire: tel que , si puis . Je cherche un algorithme pour trouver tous les éléments minimaux de , c'est-à-dire les tels que mais , . Puisque la largeur de est n \ choisissez n /...
Inspiré par cette question , je suis curieux de savoir ce qui suit: Quelle est la pire des situations pour vérifier si un DFA donné accepte le même langage qu'une expression régulière donnée? Est-ce connu? L'espoir serait que ce problème soit en P - qu'il existe un algorithme polynomial dans la...
est largement supposé être faux.R P= NPRP=NPRP = NP Mais imaginez un instant que c'est vrai. Dans ce cas, quelle serait la probabilité que ?P= NPP=NPP = NP En d'autres termes: dans un monde où , qu'est-ce qui pourrait encore être considéré comme un obstacle pour nous de croire P = N P ?R P=...
L'algorithme simplex est souvent traité soit dans l'arithmétique réelle, soit dans le monde discret avec des calculs exacts. Cependant, il semble être implémenté le plus souvent avec une arithmétique à virgule flottante. Cela conduit à se demander si l'algorithme simplex doit être considéré comme...
Le théorème de dichotomie de Schaefer montre que chaque problème de CSP sur est soit résoluble en temps polynomial, soit NP-complet. Cela s'applique uniquement aux problèmes CSP de largeur limitée, à l'exclusion de SAT et Horn-SAT, par exemple. Les problèmes CSP généraux de largeur illimitée...
Considérons un circuit qui prend comme nombres d'entrées dans [0,1][0,1][0,1] et a des portes qui se composent des fonctions max(x,y)max(x,y)\max(x, y) , min(x,y)min(x,y)\min(x, y) , 1−x1−x1 - x et x+y2x+y2\frac{x+y}{2} . La sortie du circuit est alors également un nombre en [0,1][0,1][0,1] ....
Le célèbre article de 1983 de H. Lenstra Integer Programming With A Fixed Number Of Variables indique que les programmes entiers avec un nombre fixe de variables peuvent être résolus dans le polynôme temporel dans la longueur des données. J'interprète cela comme suit. La programmation entière en...
aaabbbaaabbbaaabbbO(mlogmloglogm)O(mlogmloglogm)O(m\log m\log\log m)mmmmax{a,b}max{a,b}\max\{a,b\}Ω(mlogmloglogm)Ω(mlogmloglogm)\Omega(m\log m\log\log m) la limite inférieure de ce problème? Merci et salutations, et désolé si c'est une question aussi
Je recherche des résultats de dureté sur la coloration des sommets des graphiques à degré borné. Étant donné un graphique , nous savons que pour tout ϵ > 0 , il est difficile d'approximer χ ( G ) dans un facteur de | V | 1 - ϵ sauf si NP = ZPP [ 1 ]. Mais que se passe-t-il si le degré maximal de...
Sudoku est un puzzle bien connu qui est NP-complet. Le Sudoku binaire est une variante qui n'autorise que les chiffres et 1 . Les règles sont les suivantes.000111 Chaque ligne et chaque colonne doit contenir un nombre égal de zéros et de uns. Chaque ligne et chaque colonne est unique. Aucune ligne...
Définissez comme la classe de langues pouvant être acceptée par une machine de Turing (multitape) dans le temps . (Le " " est juste pour simplifier la notation et éviter toute confusion.) Notez qu'il n'y a pas de autour de .f ( n ) + 1 + 1 O ( ⋅ ) f ( n ) + 1D T I M E (f( n )...
Je cherche un petit graphe GGG dont le nombre chromatique vectoriel est plus petit que le nombre chromatique,
L'analyse lissée a été appliquée à plusieurs reprises pour comprendre le temps d'exécution d'algorithmes exacts pour de nombreux problèmes comme la programmation linéaire et les k-means. Il existe des résultats assez généraux dans ce domaine, par exemple Heiko Röglin et Berthold Vöcking, Smoothed...
Quelle est la relation entre PLSPLS\mathsf{PLS} et APXAPX\mathsf{APX} ? En d'autres termes, les problèmes qui admettent une recherche locale en temps polynomial sont-ils approximables? Les problèmes d'optimisation approximatifs impliquent-ils un algorithme de recherche local en
Je fais actuellement des recherches sur le langage formel impliquant des classes de langues au-dessus de Regular mais en dessous de Context Free. Je regarde des choses comme les machines à compteurs multiples inversées, les compteurs à pile unique, les LFC déterministes, etc. Je me demande si...