Pourquoi la plupart des gens préfèrent-ils utiliser plusieurs réductions pour définir l'exhaustivité des NP au lieu, par exemple, des réductions de
Il est communément admis que pour tout , il est possible de multiplier deux matrices en un temps . Une discussion est ici .ϵ>0ϵ>0\epsilon > 0n×nn×nn \times nO(n2+ϵ)O(n2+ϵ)O(n^{2 + \epsilon}) J'ai demandé à des personnes plus familières avec les recherches si elles pensaient qu'il y avait un...
Ryan Williams vient d’afficher sa limite inférieure sur ACC , la classe de problèmes qui ont des circuits de profondeur constante avec des ouvertures et des portes sans bornes AND, OR, NOT et MOD_m pour tous les m possibles. Qu'est-ce qui rend les portes MOD_m si spéciales? Ils permettent de...
Le théorème d'Immerman-Vardi stipule que PTIME (ou P) est précisément la classe de langages pouvant être décrite par une phrase de la logique du premier ordre avec un opérateur à point fixe, sur la classe des structures ordonnées. L'opérateur de point fixe peut être soit le point le moins fixe...
On prétend parfois que la théorie de la complexité géométrique de Ketan Mulmuley est le seul programme plausible pour régler les questions en suspens de la théorie de la complexité, comme la question P vs NP. Plusieurs théoriciens de la complexité connus ont commenté positivement le programme....
La cupidité, faute d'un meilleur mot, est bonne. L' approche gloutonne est l'un des premiers paradigmes algorithmiques enseignés dans le cours d'introduction aux algorithmes . Une approche gloutonne donne des algorithmes simples et intuitifs pour de nombreux problèmes de P. Plus intéressant, pour...
Un certain nombre de problèmes géométriques sont faciles à prendre en compte dans , mais sont NP-complets dans R d pour d ≥ 2 (y compris l'un de mes problèmes préférés, le cache du disque de l'unité).R1R1R^1RdRdR^dd≥2d≥2d\geq2 Est-ce que quelqu'un connaît un problème qui peut être résolu à tout...
La classe de complexité comprend les problèmes de qui peuvent être résolus par une machine de Turing polynomiale non déterministe qui en a au plus un qui accepte le chemin de calcul. C'est-à-dire que la solution, s'il y en a une, est unique en ce sens. Il est hautement improbable que tous les...
Je m'intéresse à la complexité paramétrée de ce que j'appellerai le problème d'ensemble d-dimensionnel: donné un espace de plage (c'est-à-dire un ensemble système / hypergraphe) S = (X, R) ayant une dimension VC au plus d et a entier positif k, X contient-il un sous-ensemble de taille k qui touche...
Cette question est inspirée d'une question similaire sur les mathématiques appliquées sur mathoverflow, et cette pensée persistant pensait que des questions importantes du TCS telles que P vs NP pourraient être indépendantes de ZFC (ou d'autres systèmes). Comme arrière-plan, les mathématiques...
Nous savons que le premier niveau de la hiérarchie polynomiale (c'est-à-dire NP et co-NP) est en PP, et que . Le théorème de Toda indique également que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Savons-nous si ? Si non, pourquoi est-ce que avec un oracle en est plus fort...
Autant que je sache, le programme de théorie de la complexité géométrique tente de séparer en prouvant que le permament d'une matrice à valeurs complexes est beaucoup plus difficile à calculer que le déterminant.VP≠VNPVP≠VNPVP \neq VNP Après avoir parcouru les documents du GCT, la question que je...
En général, nous savons qu'il est plus facile de tester si une fonction prend une valeur particulière à une entrée donnée que d'évaluer la fonction à cette entrée. Par exemple: L'évaluation du permanent d'une matrice de nombre entier non négatif est # P-difficile, mais indiquer si un tel permanent...
Étant donné un nouveau problème dans dont la véritable complexité se situe quelque part entre et NP-complete, il existe deux méthodes que je connais qui pourraient être utilisées pour prouver que la résolution de ce problème est difficile:NPNP\mathsf{NP}PP\mathsf{P} Montrer que le problème est...
Il est facile de décider si un équilibre de Nash existe. cependant, en trouver un est difficile (PPAD-Complete). Quels sont quelques autres exemples de problèmes où la version de décision est facile mais la version de recherche est relativement difficile (comparée à la version de décision)? Je...
C'est une question non technique, mais certainement pertinente pour la communauté du SDC. Si jugé inapproprié, n'hésitez pas à fermer. La page Web Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) a certainement rendu de grands services à la communauté TCS au fil des ans....
Une application importante du théorème PCP est qu'il donne des résultats de type "dureté d'approximation". Dans certains cas relativement simples, on peut prouver une telle dureté sans PCP. Existe-t-il toutefois des cas où la dureté du résultat de l'approximation a d'abord été prouvée à l'aide du...
Dans l'introduction et l'explication, les classes de complexité P et NP souvent données par la machine de Turing. L'un des modèles de calcul est le lambda-calcul. Je comprends que tous les modèles de calcul sont équivalents (et si nous pouvons introduire n'importe quoi en termes de machine de...
On suppose que le caractère aléatoire n’étend pas la puissance des algorithmes de temps polynomiaux, c’est-à-dire que est supposé tenir. D'autre part, le hasard semble avoir un effet assez différent sur les réductions de temps polynomiales . Selon le résultat bien connu de Valiant et Vazirani, la...
Nous savons que la fonction exponentielle sur les nombres naturels n'est pas calculable en temps polynomial, car la taille de la sortie n'est pas polynomiale dans la taille des entrées.exp( x , y) = xyexp(x,y)=xy\exp(x,y) = x^y Est-ce la raison principale de la difficulté de calculer la fonction...