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 ....
Récemment, Watrous et al ont prouvé que QIP (3) = PSPACE un résultat remarquable. Ce fut pour moi un résultat surprenant pour le moins et cela m'a fait réfléchir ... Je me demandais si les ordinateurs quantiques pouvaient être simulés efficacement par les ordinateurs classiques. Serait-ce...
Suite à la suggestion de Josh Grochow, je convertis mon commentaire d'une question précédente en une nouvelle question. Quelles preuves avons-nous pour ?U P ≠ N PUP≠NP\mathsf{UP} \neq \mathsf{NP} Ici est la classe de langages reconnaissable par les machines de Turing non déterministes à temps...
Dans nos travaux récents, nous résolvons un problème de calcul qui s'est posé dans un contexte combinatoire, en supposant que , où ⊕EXP≠⊕EXPEXP≠⊕EXP\mathsf{EXP} \ne \mathsf{\oplus{}EXP} est la version E X P de ⊕⊕EXP⊕EXP\mathsf{\oplus{}EXP}EXPEXP\mathsf{EXP} . Le seul papier sur...
Une question récente (voir les conséquences de NP = PSPACE ) a demandé des conséquences "désagréables" de . Les réponses liste assez peu de conséquences de l' effondrement, y compris N P = c o N P et d' autres, en fournissant beaucoup de raisons de croire N P ≠ P S P A C E...
Nous savons que si alors tout le PH s'effondre. Et si la hiérarchie polynomiale s'effondre partiellement? (Ou comment comprendre que le PH pourrait s'effondrer au-dessus d'un certain point et non en dessous?)P=NPP=NPP=NP En termes plus courts, quelles seraient les conséquences de et ?P ≠ N...
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=...
P/ poly= NP/ polyP/poly=NP/polyP/poly = NP/poly impliqueNP⊆ P/ polyNP⊆P/polyNP \subseteq P/poly , qui à son tour a des conséquences intéressantes comme l'effondrement de la hiérarchie polynomiale. Y a-t-il des implications intéressantes pour P/ poly≠ NP/ polyP/poly≠NP/polyP/poly \neq NP/poly...
en 1979 Hopcroft / Ullman a écrit que L ⊆ P ⊆ NP ⊆ PSpace est connu mais L ⊊ PSpace est le seul confinement approprié (et trivial) connu bien que tous soient supposés être des confinements appropriés, et "où les choses se tiennent encore" ~ 4 décennies plus tard . depuis lors, existe-t-il des liens...
Étant donné telle sorte que les coefficients de p , q soient bornés par B , est-ce que p ≡ q est vrai ?p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Le lemme de Schwartz-Zippel s'applique ici car...
Est-ce que implique