Je suis intéressé par la généralisation naturelle du célèbre casse-tête de 15 , dans laquelle vous devez faire glisser des blocs jusqu'à ce que vous ayez trié tous les nombres donnés (généralement, il y a un écart d'un bloc). La généralisation consisterait maintenant à étendre la taille du puzzle...
Le zoo de complexité souligne dans l'entrée sur EXP que si L = P, alors PSPACE = EXP. Depuis NPSPACE = PSPACE par Savitch, dans la mesure où je peux dire, l’argument de remplissage de base sous-jacent s'étend pour montrer que Nous savons également que L NL NC P via la hiérarchie alternée liée aux...
Ceci est une question naïve, de mon expertise; excuses à l'avance. La conjecture de Goldbach et de nombreuses autres questions non résolues en mathématiques peuvent être écrites sous forme de formules courtes dans le calcul des prédicats. Par exemple, le document de Cook "Les ordinateurs...
La complexité informatique comprend l’étude de la complexité temporelle ou spatiale des problèmes informatiques. Du point de vue de l'informatique mobile, l'énergie est une ressource informatique précieuse. Alors, existe-t-il une adaptation bien étudiée des machines de Turing qui prend en compte...
Papadimitriou écrit dans son livre "Computational Complexity": RP est en quelque sorte un nouveau type de classe de complexité inhabituel. Nulle machine de Turing non déterministe à bornes polynomiales ne peut être à la base de la définition d’un langage dans RP. Pour qu'une machine N définisse une...
SoitAAA un entier positif fixe de taille nnn bits. On est autorisé à prétraiter cet entier comme il convient. Etant donné un autre entier positif BBB de taille mmm bits, quelle est la complexité de la multiplication ABABAB ?
Récemment, Gil Kalai et Dick Lipton ont tous deux écrit un bel article sur une hypothèse intéressante proposée par Peter Sarnak, expert en théorie des nombres et Hypothèse de Riemann. Conjecture. Soit la fonction de Möbius . Supposons que soit une fonction avec entrée sous la forme d'une...
Quels ont été les résultats les plus surprenants en complexité? Je pense qu’il serait utile d’avoir une liste de résultats inattendus / surprenants. Cela inclut à la fois des résultats surprenants et sortis de nulle part et des résultats qui se sont révélés différents de ceux attendus. Edit : étant...
Le problème de bande passante minimum est de trouver un ordre des nœuds de graphe sur une ligne entière qui minimise la distance la plus grande entre deux nœuds adjacents quelconques. Une chenille est un arbre formé à partir de la trajectoire principale par la croissance de trajectoires dont les...
Beaucoup pensent que . Cependant, nous savons seulement que est dans le deuxième niveau de la hiérarchie polynomiale, c'est-à-dire . Un pas vers montrant B P P = P est d'abord de faire descendre au premier niveau de la hiérarchie polynomiale, soit B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} =...
L'affacturage n'est pas connu pour être NP-complet. Cette question portait sur les conséquences de la factorisation de NP-complet. Curieusement, personne n’a demandé les conséquences de l’affacturage dans P (peut-être parce qu’une telle question est triviale). Donc mes questions sont: Quelles...
Nous entendons souvent parler de recherches classiques et de publications dans le domaine de la complexité informatique (Turing, Cook, Karp, Hartmanis, Razborov, etc.). Je me demandais s'il y avait des articles récemment publiés considérés comme essentiels et à lire absolument. Récemment, je veux...
Il y a quelques années, Joel Friedman avait écrit un article reliant les limites inférieures du circuit à la cohomologie de Grothendieck (voir articles: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Cette ligne de pensée a-t-elle apporté de nouvelles informations sur la...
Le problème central de la théorie de la complexité est sans doute vs N P .PPPNPNPNP Cependant, comme la nature est quantique, il semblerait plus naturel de considérer les classes (c'est-à-dire les problèmes de décision pouvant être résolus par un ordinateur quantique en temps polynomial, avec une...
Du point de vue du sens commun, il est facile de croire que l’ajout du non-déterminisme à PP\mathsf{P} étend considérablement son pouvoir, c’est-à-dire que NPNP\mathsf{NP} est beaucoup plus grand que PP\mathsf{P} . Après tout, le non-déterminisme permet un parallélisme exponentiel, qui apparaît...
Nous savons que si vous avez une machine PSPACE, elle est suffisamment puissante pour donner une preuve interactive de la hiérarchie polynomiale à n’importe quel niveau. (Et si je me souviens bien, tout ce que vous avez besoin est #P.) Mais si vous voulez donner une preuve interactive de l'...
En 1995, Russell Impagliazzo a proposé cinq mondes de complexité: 1- Algorithmique: P= NPP=NPP=NP avec toutes les conséquences étonnantes. 2- Heuristica: problèmes complets sont difficiles dans le pire des cas ( P ≠ N PNPNPNPP≠ NPP≠NPP \ne NP ) mais sont efficacement résolubles dans le cas moyen....
En tant qu'amateur de TCS, je lis du matériel très introductif sur l'informatique quantique. Voici les quelques informations élémentaires que j'ai apprises jusqu'à présent: Les ordinateurs quantiques ne sont pas connus pour résoudre des problèmes NP-complets en temps polynomial. "La magie quantique...
J'ai suivi un cours une fois sur la calculabilité et la logique. Le matériel comprenait une corrélation entre les classes de complexité / calculabilité (R, RE, co-RE, P, NP, Logspace, ...) et la logique (Calcul de prédicats, logique du premier ordre, ...). La corrélation comprenait plusieurs...
Considérez le problème de comptage suivant (ou le problème de décision associé): Étant donné deux entiers positifs codés en binaire, calculez leur plus grand commun diviseur (gcd). Quelle est la plus petite classe de complexité dans laquelle ce problème est contenu? Pouvez-vous fournir une...