capture l'idée d'une parallélisation efficace, et une interprétation de celui-ci est les problèmes qui peuvent être résolus dans le temps O ( log c n ) en utilisantdes processeurs parallèles O ( n k ) pour certaines constantes c , k . Ma question est de savoir s'il existe une classe de complexité...
Y a-t-il un exemple d'un problème naturel qui est dans BPP mais qui n'est pas connu pour être RP ou
Inspiré par la question de l' affacturage connu pour être P-dur , je me demande quel est l'état similaire actuel des connaissances sur la dureté de l'isomorphisme du graphe. Je suis sûr que l'on ne sait pas actuellement si GI est en P, mais: quelle est la plus grande classe actuellement connue que...
Je sais que la complexité de la plupart des variétés de calculs lambda typés sans la primitive combinateur Y est bornée, c'est-à-dire que seules les fonctions de complexité bornée peuvent être exprimées, la borne devenant plus grande à mesure que l'expressivité du système de types croît. Je...
BQP est-il égal à BPP avec accès à un oracle de sous-groupe caché
Je suis curieux au sens large de ce que l'on sait des algorithmes de parallélisation en P. J'ai trouvé l'article wikipedia suivant sur le sujet: http://en.wikipedia.org/wiki/NC_%28complexity%29 L'article contient la phrase suivante: On ne sait pas si NC = P, mais la plupart des chercheurs...
Discussion : J'ai passé un peu de temps récemment à apprendre différentes choses sur la complexité de la communication. Par exemple, je me suis familiarisé avec le chapitre pertinent d'Arora / Barak, j'ai commencé à lire certains articles et commandé le livre de Kushilevitz / Nisan. Intuitivement,...
Les langages foliaires sont une belle façon de définir uniformément de nombreuses classes de complexité. La plupart des classes de complexité sont généralement spécifiées par un modèle de calcul (par exemple, TM déterministe / randomisé) et une ressource liée (temps logarithmique, espace poly,...
Aujourd'hui à New York et dans le monde entier, l'anniversaire de Christos Papadimitriou est célébré. C'est une bonne occasion de poser des questions sur les relations entre la classe de complexité PPAD de Christos (et ses autres classes apparentées) et les ordinateurs quantiques. Dans son célèbre...
Disons qu'un langage est de densité P proche s'il existe un algorithme de temps polynomial qui décide correctement sur presque toutes les entrées.LLLLLLL En d'autres termes, il existe un P , tel que disparaît, ce qui signifie Cela signifie également que sur une entrée aléatoire uniforme,...
Existe-t-il un exemple d'une classe de graphes pour laquelle le problème de coloration des sommets est en P mais l'ensemble indépendant est le problème est NP
La parité et sont comme des jumeaux inséparables. Ou du moins, cela semble au cours des 30 dernières années. À la lumière du résultat de Ryan, il y aura un regain d'intérêt pour les petites classes.AC0AC0AC^0 Furst Saxe Sipser à Yao à Hastad sont toutes des restrictions de parité et aléatoires....
Laissez un entier fonction d'une valeur telle que 2 F est en # P . S'ensuit-il que F est en # P ? Y a-t-il des raisons de croire qu'il est peu probable que cela tienne toujours? Des références que je devrais connaître?FFF2F2F2F#P#P\#PFFF#P#P\#P De façon assez surprenante, cette situation est...
Wikipédia a énuméré quatre problèmes qui sont en mais qui sont supposés être en dehors de P : factorisation entière; Logarithme discret; Simulation de systèmes quantiques; Calcul du polynôme de Jones à certaines racines de l'unité.B Q PBQPBQPPPP Existe-t-il d'autres problèmes de ce...
EDIT au 2011/02/08: Après avoir trouvé et lu des références, j'ai décidé de séparer la question d'origine en deux questions distinctes. Voici la partie concernant UP vs NP, pour la partie classes syntaxiques et sémantiques, veuillez consulter Avantages pour les classes syntaxiques et sémantiques ....
Y a-t-il des références qui fournissent des détails sur les limites inférieures du circuit pour des problèmes difficiles spécifiques survenant en cryptographie tels que l'affacturage entier, problème de logarithme discret premier / composite et sa variante sur un groupe de points de courbes...
La célèbre conjecture d'isomorphisme de Berman et Hartmanis dit que tous langages complets sont isomorphes en temps polynomiaux (p-isomorphes) les uns aux autres. La signification clé de la conjecture est qu'elle implique . Il a été publié en 1977, et une preuve à l'appui était que tous problèmes...
Le zoo de complexité n'a pas grand-chose sur . Je recherche un joli problème qui se situe aux niveaux supérieurs de la hiérarchie, c'est-à-dire un problème dans mais dans .SCSC\mathsf{SC} † D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n) D T i m e S p a c e ( n O ( 1 ) , lg 2...
Problème: on nous donne un ensemble de bâtons ayant tous des longueurs entières. La somme totale de leurs longueurs est n (n + 1) / 2. Pouvons-nous les casser pour obtenir des bâtons de taille en temps polynomial? 1 , 2 , … , n1,2,…,n{1,2,\ldots,n} Étonnamment, la seule référence que je trouve pour...
La parité-P 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). Ainsi la parité-P est essentiellement PP jeune frère...