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...
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...
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...
La plupart des algorithmes bien connus sont du premier ordre, en ce sens que leur entrée et leur sortie sont des données "simples". Certaines sont de second ordre de manière triviale, par exemple le tri, les hashtables ou les fonctions map et fold: elles sont paramétrées par une fonction, mais...
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...
En substance, la question est: Quelle est l'unité la moins publiable pour ArXiv? Les domaines qui utilisent beaucoup ArXiv, tels que l'informatique quantique, présentent un intérêt particulier. Mais les commentaires sur d'autres domaines et les services de pré-impression (comme ECCC et ePrint) sont...
Quand nous suivons les manuels standard, ou la tradition, la plupart d' entre nous enseignent la définition suivante de la notation grand-Oh dans les premières conférences d'une classe d'algorithmes: f=O(g) iff (∃c>0)(∃n0≥0)(∀n≥n0)(f(n)≤c⋅g(n)).f=O(g) iff (∃c>0)(∃n0≥0)(∀n≥n0)(f(n)≤c⋅g(n)). f...
Le problème est de calculer le polynôme . Supposons que tous les coefficients tiennent dans un mot machine, c’est-à-dire qu’ils puissent être manipulés dans le temps unitaire.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Vous pouvez faire fois en appliquant...
La preuve standard de la borne de Chernoff (du manuel Randomized Algorithms ) utilise les fonctions d'inégalité de Markov et de génération de moments, avec un peu de développement de Taylor, rien de trop difficile, mais plutôt mécanique. Mais il existe d'autres preuves liées de Chernoff qui...
Une des questions les plus discutées sur le site a été Qu'est-ce que cela signifierait de réfuter la thèse de Church-Turing ? C'est en partie parce que Dershowitz et Gurevich ont publié une preuve de la thèse de Church-Turing est le Bulletin de la logique symbolique de 2008. (Je n'en discuterai pas...
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...
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 ?
Je suis un étudiant de première année en informatique et je sais déjà que je veux aller dans le monde universitaire avec une concentration en science-fiction théorique. J'ai déjà lu certains des articles référencés dans cette question et cette question m'a convaincu davantage. Que devrais-je faire...
Soit un graphe avec la fonction de poids . Le problème de max-cut consiste à trouver: Si la fonction de pondération n'est pas négative (c'est-à-dire w (e) \ geq 0 pour tous les e \ à E ), il existe alors de nombreuses approximations 2 extrêmement simples pour max-cut. Par exemple, nous...
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...
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...
On pense généralement à l’approximation des solutions (avec des garanties) aux problèmes difficiles à résoudre. Y a-t-il des recherches en cours sur l'approximation des problèmes déjà connus comme étant en P? Cela pourrait être une bonne idée pour plusieurs raisons. De prime abord, un algorithme...
Mark Dominus a rassemblé quelques exemples de réduction du temps polynomial de divers problèmes NP-difficiles à la correspondance «d'expression régulière» . Envisager des vérifications en temps polynomial n'est pas un énorme pas en avant. Comment illustrez-vous la classe NP-complete aux étudiants...
Existe-t-il une structure de données qui prend un tableau non ordonné de éléments, effectue un prétraitement dans et répond aux requêtes: existe-t-il un élément dans la liste, chaque requête au pire moment ?O ( n ) x O ( log n )nnnO ( n )O(n)O(n)XXxO ( logn )O(bûchen)O(\log n) Je pense vraiment...