Je cherche des exemples de problèmes paramétrés par un nombre , où la dureté du problème est non monotone en . La plupart des problèmes (selon mon expérience) ont une transition de phase unique, par exemple -SAT a une transition de phase unique de (où le problème est en P) à (où le le problème est...
Connaissez-vous des algorithmes sensés fonctionnant en temps polynomial en (Longueur d’entrée + longueur en sortie), mais dont le temps de fonctionnement asymptotique dans la même mesure a un exposant / une constante vraiment énorme (au moins, où la limite supérieure prouvée du temps de...
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...
Récemment, quand j'ai parlé à un physicien, j'ai affirmé que, selon mon expérience, lorsqu'un problème qui semble naïvement prendre un temps exponentiel se révèle non trivialement en P ou en BPP, il est généralement possible d'identifier une "raison primordiale" de la réduction. --- et presque...
Quels outils utilisez-vous pour écrire des papiers? Du fait de mon peu d’expérience, les théoriciens passent beaucoup de temps à écrire et à peaufiner des papiers, en plus d’être réellement créatifs. C'est-à-dire communiquer leur travail à d'autres personnes. Peut-être que les papiers ne sont pas...
Quels sont vos exemples préférés dans lesquels la théorie de l’information est utilisée pour prouver de façon simple une déclaration combinatoire nette? Certains exemples auxquels je peux penser sont liés aux limites inférieures pour les codes localement décodables, par exemple, dans cet article:...
Deux manières d’analyser l’efficacité d’un algorithme sont: mettre une limite supérieure asymptotique sur son temps d'exécution, et pour l'exécuter et collecter des données expérimentales. Je me demande s’il existe des cas connus où il existe un écart important entre (1) et (2). Par cela, je veux...
On me demande souvent ce que fait un informaticien théorique. Ce serait bien d'avoir de bonnes réponses à cette question. J'ai tendance à retomber dans le jargon technique et les yeux des gens brillent généralement à ce stade. Que fait un informaticien théorique en termes compréhensibles par des...
Cette question s'inspire d' une autre question sur les nouveautés du PFDS depuis la publication du livre d'Okasaki en 1998 . Je vais commencer par deux questions que j'ai: Existe-t-il une structure de données d'ensemble purement fonctionnelle qui approche la vitesse des tables de hachage? Les...
Après une question fructueuse dans MO , j’ai pensé qu’il serait intéressant de discuter de noms de papier notables dans CS. Il est clair que la plupart d’entre nous pourraient être attirés par la lecture (ou au moins jeter un coup d’œil sur un article avec un titre intéressant) (du moins je le fais...
Aujourd'hui, Ryan Williams a publié un article sur arXiv (précédemment publié dans SIGACT News) contenant une version moins technique de sa récente technique de limite inférieure ACC . Ma question ne concerne pas la technique elle-même (bien sûr mérite des éloges), mais concerne le style du papier....
De manière informelle, la complexité de Kolmogorov d'une chaîne est la longueur d'un programme le plus court qui génère x . Nous pouvons définir une notion de 'chaîne aléatoire' en l'utilisant ( x est aléatoire si K ( x ) ≥ 0,99 | x | ) Il est facile de voir que la plupart des chaînes sont...
J'écris actuellement une enquête sur les théorèmes de hiérarchie sur le TCS. En recherchant des articles apparentés, j'ai remarqué que la hiérarchie était un concept fondamental non seulement dans les domaines du SDC et des mathématiques, mais également dans de nombreuses sciences, allant de la...
Sur MathOverflow, Timothy Gowers a posé une question intitulée " Démontrer que la rigueur est importante ". La plupart des discussions ont porté sur des cas montrant l’importance de la preuve, dont les utilisateurs de CSTheory n’ont probablement pas besoin d’être convaincus. Selon mon expérience,...
Quelles sont les applications théoriques des codes de correction d'erreur en plus de la correction d'erreur elle-même? Je connais trois applications: le théorème de Goldreich-Levin sur le trépan dur, la construction d’un extracteur par Trevisan et l’ amplification de la dureté de la fonction...
Le théorème des quatre couleurs (4CT) stipule que chaque graphe planaire peut être coloré en quatre. [Appel, Haken 1976] et [Robertson, Sanders, Seymour, Thomas 1997] ont donné deux preuves. Ces deux preuves sont assistées par ordinateur et assez intimidantes. Il existe plusieurs conjectures en...
Il semble que la théorie de la complexité géométrique nécessite une connaissance approfondie des mathématiques pures telles que la géométrie algébrique, la théorie de la représentation. Bien que je sois un étudiant en informatique et que je n’ai PAS de cours de mathématiques très abstraites et...
Le problème de la somme des racines carrées pose, étant donné deux séquences a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n et b1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n d’entiers positifs, si la somme inférieure à, égale à to, ou supérieure à la somme . Le statut de complexité de ce problème est ouvert;...
Il est facile de décider si un équilibre de Nash existe. cependant, en trouver un est difficile (PPAD-Complete). Quels sont quelques autres exemples de problèmes où la version de décision est facile mais la version de recherche est relativement difficile (comparée à la version de décision)? Je...
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...