Problèmes connus pour être ouverts dans la littérature et tout problème qui, après avoir été posé, est décidé à être ouvert par la communauté.
Wikipedia n'énumère que deux problèmes sous "problèmes non résolus en informatique" : P = NP? L'existence de fonctions à sens unique Quels sont les autres problèmes majeurs qui devraient être ajoutés à cette liste? Règles: Un seul problème par réponse Fournir une brève description et tout lien...
Un mélange de deux chaînes est formé en intercalant les caractères dans une nouvelle chaîne, en maintenant les caractères de chaque chaîne dans l'ordre. Par exemple, MISSISSIPPIest un mélange de MISIPPet SSISI. Permettez-moi d'appeler un carré de corde s'il s'agit d'un mélange de deux chaînes...
Contexte Il y a plusieurs années, lorsque j'étais étudiant de premier cycle, on nous a confié un devoir d'analyse en amortissement. J'ai été incapable de résoudre l'un des problèmes. Je l’avais demandé en théorie , mais aucun résultat satisfaisant n’a été obtenu. Je me souviens du cours TA a...
Après avoir étudié les automates à états finis (DFA) déterministes chez les étudiants de premier cycle, j’ai eu le sentiment qu’ils étaient extrêmement bien compris. Ma question est de savoir s'il y a quelque chose que nous ne comprenons toujours pas à leur sujet. Je ne parle pas de généralisations...
Dans le fil Problèmes majeurs non résolus en informatique théorique? Iddo Tzameret a formulé l’excellent commentaire suivant: Je pense que nous devrions faire la distinction entre les grands problèmes ouverts qui sont considérés comme des problèmes fondamentaux, comme , et les grands problèmes...
Considérons familles disjointes de sous-ensembles de {1,2,…, n}, F 1 , F 2 , … F t .tttF1, F2, … FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Supposer que (*) Pour chaque et chaque R ∈ F i , et T ∈ F k , il existe S ∈ F j qui contient R ∩ T .je < j < ki<j<ki \lt j \lt kR ∈ FjeR∈FiR...
Mise à jour : L'ensemble des obstructions (c'est-à-dire la "barrière" NxM entre les tailles de grille colorables et non colorables) pour toutes les couleurs 4 monochromes sans rectangle est maintenant connu . Quelqu'un veut-il essayer 5 couleurs? ;) La question suivante découle de la théorie de...
Ce problème s’inspire de cette question du MO , que j’ai trouvée très intéressante. Quel est le problème ouvert le plus ancien dans TCS? Il est clair que cette question nécessite des éclaircissements. Tout d'abord, qu'est-ce que le TCS? Je pense que l'existence de nombres impairs parfaits n'est pas...
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...
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...
Dans l'esprit de certaines discussions générales comme celle- ci, j'ouvre ce fil avec l'intention de recueillir des opinions sur les défis ouverts et les sujets brûlants de la recherche sur les langages de programmation . J'espère que la discussion pourra même faire émerger des opinions sur...
Je voudrais poser une question sur un cas particulier de la question « Décider si un circuit NC 0 donné calcule une permutation » par QiCheng qui est resté sans réponse. Un circuit booléen est appelé circuit NC 0 k si chaque porte de sortie dépend syntaxiquement d'au plus k portes d'entrée. (Nous...
Le problème suivant est-il NP-difficile? Étant donné une configuration de carte pour brouillons internationaux , trouvez un mouvement juridique unique.n×nn×nn\times n Le problème correspondant pour les vérificateurs américains (ou versions anglaises) est trivialement résoluble en temps polynomial....
Est un algorithme déterministe à temps polynomial connu pour le problème suivant: Entrée: un nombre naturel (en encodage binaire)nnn Sortie: un nombre premier .p > np>np > n (Selon une liste de problèmes ouverts par Leonard Adleman, le problème était ouvert en 1995.)
Le rang de signe d'une matrice A avec + 1, -1 entrées est le plus petit rang (sur les réels) d'une matrice B qui a le même motif de signe que A (c'est-à-dire pour tous ). Cette notion est importante dans la complexité de la communication et la théorie de l'apprentissage.UNEje jBje j>...
Pour une constante , on peut déterminer en temps linéaire, étant donné un graphe d'entrée G , si sa largeur d'arbre est ≤ k . Cependant, lorsque k et G sont donnés en entrée, le problème est NP-difficile. ( Source ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Cependant, lorsque le graphe d'entrée est...
En 1999, Petra Schuurman et Gerhard J. Woeginger ont publié l'article "Algorithmes d'approximation du temps polynomiaux pour la planification des machines: dix problèmes ouverts" . Depuis lors, à ma connaissance, des critiques qui concerneraient très exactement la même liste de problèmes ne sont...
Supposons que l'on nous donne plusieurs polygones simples disjoints dans le plan, et deux points et t à l' extérieur de chaque polygone. Le problème du chemin le plus court euclidien consiste à calculer le chemin le plus court euclidien de s à t qui ne coupe pas l'intérieur d'un polygone. Pour être...
Outre la complexité de communication (déterministe) d'une relation , une autre mesure de base pour la quantité de communication nécessaire est le numéro de partition de protocole . La relation entre ces deux mesures est connue jusqu'à un facteur constant. La monographie de Kushilevitz et Nisan...
Dans le document "A Compendium of Problems Complete for P" de Greenlaw, Hoover et Ruzzo (PS) (PDF) , il y a une liste de problèmes dans P qui ne sont pas connus pour être en NC et pas connus pour être P-complete non plus. . (Cette liste résume tous les problèmes ouverts dans l'excellente enquête de...