La question sur la théorie " Qu'est-ce que NP est limité aux témoins de taille linéaire? " Demande à propos de la classe NP limitée aux témoins de taille linéaire O ( n )O(n)O(n) , mais Existe-t-il des problèmes naturels NP-complets dans lesquels (oui) les instances de taille nécessitent des...
Dans son livre, Boolean Function Complexity, Stasys Jukna mentionne (page 564) que Kolmogorov croyait que chaque langue en P avait des circuits de taille linéaire. Aucune référence n'est mentionnée et je n'ai rien trouvé en ligne. Quelqu'un en sait-il plus
Est-il judicieux de considérer une catégorie de tous les problèmes NP-complets, avec des morphismes comme des réductions de poly-temps entre différentes instances? Quelqu'un a-t-il déjà publié un article à ce sujet, et si oui, où puis-je le
Le blog de Scott Aaronson a donné aujourd'hui une liste de problèmes / tâches ouverts intéressants en complexité. Un en particulier a retenu mon attention: Construisez une bibliothèque publique d'instances 3SAT, avec aussi peu de variables et de clauses que possible, qui aurait des conséquences...
Soit un polynôme de degré d dans n variables sur F 2 , où d est constant (disons 2 ou 3). Je voudrais trouver la plus petite formule pour f , où «formule» et «taille de formule» sont définies de manière évidente (par exemple, la plus petite formule pour le polynôme x 1 x 2 + x 1 x 3 est x 1 ( x 2 +...
Je ne connais que deux preuves du lemme de Schwartz – Zippel. La première preuve (plus courante) est décrite dans l' entrée wikipedia . La deuxième preuve a été découverte par Dana Moshkovitz. Existe-t-il d'autres preuves qui utilisent des idées sensiblement différentes?...
Fixons un codage sans préfixe des machines de Turing et une machine de Turing universelle qui en entrée (codée comme le code sans préfixe de suivi de ) sort quelles que soient sorties sur l'entrée (éventuellement les deux fonctionnant pour toujours). Définissez la complexité de Kolmogorov de , ,...
Edit : Comme Ravi Boppana l'a correctement souligné dans sa réponse et Scott Aaronson a également ajouté un autre exemple dans sa réponse , la réponse à cette question s'est avérée «oui» d'une manière à laquelle je ne m'attendais pas du tout. J'ai d'abord pensé qu'ils n'avaient pas répondu à la...
Dans de nombreux domaines, il existe des techniques canoniques que tous ceux qui travaillent dans le domaine devraient maîtriser. Par exemple, pour les réductions d'espace de journalisation, le "truc de bit" pour la composition consiste à ne pas construire la sortie complète de la fonction...
Considérons le problème 3-SAT sur n variables. Le nombre de clauses distinctes possibles est le suivant: C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. Le nombre de cas de problème est le nombre de tous les...
Nous savons que (voir, par exemple, les théorèmes 1 et 3 de [1]), en gros, dans des conditions appropriées, des fonctions qui peuvent être efficacement calculées par la machine de Turing en temps polynomial ("efficacement calculable") peuvent être exprimées par des réseaux de neurones polynomiaux...
Cette question a été migrée à partir de Computer Science Stack Exchange car il est possible d'y répondre sur Théoretics Computer Science Stack Exchange. Migré il y a 6 ans . Il semble que beaucoup de gens croient que , en partie parce qu'ils pensent que l'affacturage n'est pas résolu par le...
La parité-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" (plutôt qu'un nombre nul ou non nul de chemins d'acceptation), et qui est en outre limité à travailler dans l'espace...
Peter Shor a montré que deux des problèmes NP-intermédiaires les plus importants, l'affacturage et le problème de log discret, sont en BQP. En revanche, le meilleur algorithme quantique connu pour SAT (recherche de Grover) ne produit qu'une amélioration quadratique par rapport à l'algorithme...
Étant donné une matrice binaire par (les entrées sont ou 1 ), le problème est de déterminer s'il existe deux vecteurs binaires v 1 ≠ v 2 tels que M v 1 = M v 2 (toutes les opérations effectuées sur Z ). Ce problème est-il difficile à NP?n M 0mmmnnnMMM000111v1≠v2v1≠v2v_1 \ne v_2Mv1=Mv2Mv1=Mv2Mv_1 =...
Je voudrais poser une question sur un cas particulier de la question « Décider si un circuit NC 0 donné calcule une permutation » par QiCheng qui est resté sans réponse. Un circuit booléen est appelé circuit NC 0 k si chaque porte de sortie dépend syntaxiquement d'au plus k portes d'entrée. (Nous...
Dans ma formation en informatique, je remarque de plus en plus que la plupart des problèmes discrets sont NP-complets (au moins), alors que l'optimisation de problèmes continus est presque toujours facilement réalisable, généralement grâce à des techniques de gradient. Y a-t-il des exceptions à...
Dans le modèle à boîte noire, le problème de la détermination de la sortie d'une machine BPP sur l'entrée est le problème de comptage approximatif de la détermination de avec une erreur additive 1/3 (disons).x E r M ( x , r )M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Existe-t-il un problème...
Le problème des nnn -queens classiques demande, étant donné un entier positif nnn , s'il existe un tableau d'entiers satisfaisant aux conditions suivantes:Q[1..n]Q[1..n]Q[1..n] i1≤Q[i]≤n1≤Q[i]≤n1\le Q[i] \le n pour toutiii i ≠ jQ[i]≠Q[j]Q[i]≠Q[j]Q[i] \ne Q[j] pour touti≠ji≠ji\ne j...
Je veux savoir si la non-uniformité aide les fonctions informatiques dans la pratique. Il est facile de montrer qu'il existe des fonctions dans , de prendre n'importe quelle fonction non calculable f et de considérer le langage { 0 f ( n ) : n ∈ ω }, qui a clairement des circuits non uniformes...