Chaque fois que j'enseigne la NP-Complétude, les étudiants demandent "y a-t-il des problèmes connus pour ne pas appartenir à NP?" Comment répondriez-vous? Je leur donne généralement un problème indécidable à titre d'exemple, mais cela ne tourne souvent pas bien: (a) si je leur donne le problème de...
Cette question est motivée par une question MathOverflow de Peng Zhang . Valiant a montré que le comptage des cliques maximales dans un graphique général est # P-complet, mais que se passe-t-il si nous nous limitons aux graphiques d'incomparabilité (c'est-à-dire que nous voulons compter les...
La parité-L, également connue sous le nom de L, est l'ensemble des langages reconnus par une machine de Turing non déterministe qui ne peut distinguer qu'un nombre pair ou un nombre impair de chemins "d'acceptation". Une question connexe récente⊕⊕\oplus été posée par Niel de Beaudrap. Ma question...
Soit un carré matrice réelle A et deux vecteurs x et b de longueur n , tels que A x = b . La résolution de x par élimination gaussienne standard donne une complexité globale de presque O ( n 3 ) . Cependant, il y a des cas où la résolution (ou ε résolution -environ) pour x Coûts O ( n log ρ n ) ,...
Dans la définition de la tractabilité à paramètres fixes (forts), la limite de temps est une expression de la forme où l'instance d'entrée est ( x , k ) avec le paramètre k , p est un polynôme et f est une fonction calculable .F( k ) .p ( | x | ) ,F(k).p(|X|),f(k).p(|x|),( x , k...
J'ai une question concernant la réductibilité SERF d'Impagliazzo , Paturi et Zane et les algorithmes sous-exponentiels. La définition de SERF-réductibilité donne ce qui suit: Si P1P1P_1 est SERF-réductible à P2P2P_2 et qu'il existe un algorithme O(2εn)O(2εn)O(2^{\varepsilon n}) pour P2P2P_2 pour...
Le théorème de prétention parallèle de Raz est un résultat important dans le PCP, l'inapproximation, etc. Le théorème est fomalisé comme suit. Un jeu , où S , T , A , B sont des ensembles finis, π est une distribution sur S × T et un prédicat V : S × T × A × B → { 0 , 1 } . Définir la valeur du jeu...
Existe-t-il une preuve que l'émulation d'une machine de Turing sur une machine de Turing inconsciente ne peut pas être effectuée en moins deO(mlogm)O(mlogm)\mathcal{O}\left(m\log m\right) where mmm is the number of steps the Turing machine uses? Or is this just an upper bound? In the paper of Paul...
Je voudrais connaître l'histoire de ces deux termes: " efficace ", " faisable ". Qui les a utilisés pour le calcul / les algorithmes la première fois? (au sens moderne de ces termes, c'est-à-dire du 20e siècle). Comment sont-ils devenus courants? Comment ces deux termes ont-ils commencé à être...
Est-il connu si le problème posé par le sommet de rétroaction sur les graphes planaires non orientés de degré borné est
Quelqu'un peut-il énumérer des problèmes bien connus qui remplissent les conditions suivantes: 1. has a generalization problem that is known to be NP-complete 2. has not been proved to be NP-complete nor has a known polynomial time solution.
Il existe plusieurs résultats bien connus de limites inférieures de taille de circuit basés sur des restrictions aléatoires et le lemme de commutation .AC0AC0\mathsf{AC^0} Pouvons-nous développer un résultat de lemme de commutation pour prouver une taille de borne inférieure pour circuits T C 0...
L'élimination gaussienne rend le déterminant d'une matrice polynomiale temps calculable. La réduction de la complexité dans le calcul du déterminant, qui est autrement la somme de termes exponentiels, est due à la présence de signes négatifs alternatifs (dont le manque rend le calcul permanent est...
La plus petite formule connue pour le déterminant a la taille selon le folklore (ou selon Ran Raz dans son papier Les formules multi-linéaires pour permanent et déterminant sont de taille super-polynomiale ).nO (logn )nO(Journaln)n^{\mathcal O(\log n)} Avez-vous une référence pour cela? En...
Un algorithme de test de distribution pour une propriété de distribution P (qui n'est qu'un sous-ensemble de toutes les distributions sur [n]) est autorisé à accéder aux échantillons en fonction d'une distribution D, et doit décider (whp) si ou ( voici généralement la distance ℓ 1 ). La mesure de...
Il me semble que les experts en apprentissage automatique / exploration de données connaissent bien P et NP, mais parlent rarement de certaines des classes de complexité les plus subtiles (par exemple NC, BPP ou IP) et de leurs implications pour une analyse efficace des données. Y a-t-il une...
On dit qu'une fonction f:N→Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} est constructible dans le temps , s'il existe une machine de Turing déterministe multi-bandes MMM qui sur toutes les entrées de longueur nnn fait au plus f(n)f(n)f(n) pas et pour chaque nnn il existe une entrée de longueur nnn sur...
Il est facile de voir que si alors il y a des problèmes de recherche totaux qui ne peuvent pas être résolus en temps polynomial (créer un problème de recherche total en ayant à la fois les témoins d'appartenance et les témoins de non-adhésion).NP∩coNP≠PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq...
Le problème de partition est faiblement NP-complet car il a un algorithme de temps polynomial (pseudo-polynomial) si les entiers d'entrée sont délimités par un polynôme. Cependant, la partition 3 est un problème fortement NP-complet même si les entiers d'entrée sont délimités par un polynôme. En...
Rappelons que la largeur d'une résolution réfutation RRR d'une formule CNF FFF est le nombre maximal de littéraux dans une clause se produisant dans RRR . Pour chaque www , il existe des formules insatisfaisantes FFFdans 3-CNF st chaque réfutation de résolution de FFF nécessite une largeur d'au...