Quelles sont les explications théoriques à la réussite pratique des solveurs SAT, et quelqu'un peut-il donner un aperçu et des explications de type "wikipedia"? Par analogie, l' analyse lissée ( version arXiv ) de l'algorithme simplex explique très bien pourquoi elle fonctionne si bien dans la...
Y a-t-il des avantages à calculer la complexité temporelle d'un algorithme utilisant le calcul lambda? Ou existe-t-il un autre système conçu à cet effet? Toute référence serait
Dans un autre fil de discussion , Joe Fitzsimons s'est interrogé sur "la meilleure limite inférieure actuelle de 3SAT". J'aimerais faire l'inverse: quelle est la meilleure limite supérieure actuelle sur 3SAT? En d'autres termes, quelle est la complexité temporelle du solveur SAT le plus efficace?...
Quelqu'un peut-il fournir une explication concise de l'approche GCT de Mulmuley compréhensible par les non-experts? Une explication qui conviendrait pour une page Wikipedia sur le sujet (qui est stub pour le moment). Motivation: Je suis en train de "co-lire" l'ouvrage de Scott Aaronson sur...
Je pense au problème suivant: je veux trouver une expression régulière qui correspond à un ensemble particulier de chaînes (par exemple, des adresses électroniques valides) et ne correspond à aucune autre (adresses électroniques non valides). Supposons que par expression régulière, nous entendons...
Il semble clair qu'un certain nombre de sous-domaines de l'informatique théorique ont été fortement influencés par les résultats de la physique théorique. Deux exemples de ceci sont Calcul quantique Résultats de la mécanique statistique utilisés dans l'analyse de complexité / les algorithmes...
Inspiré par cette question et en particulier par le dernier paragraphe de la réponse de Ou, j'ai la question suivante: Connaissez-vous des applications de la théorie de la représentation du groupe symétrique dans TCS? Le groupe symétrique est le groupe de toutes les permutations de avec une...
Les ordinateurs réels ont une mémoire limitée et seulement un nombre fini d'états. Donc, ce sont essentiellement des automates finis. Pourquoi les informaticiens théoriques utilisent-ils les machines de Turing (et d’autres modèles équivalents) pour étudier les ordinateurs? Quel est l'intérêt...
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,...
Malgré plusieurs années de cours, je ne suis toujours pas au bon endroit pour choisir un sujet de recherche. J'ai examiné des papiers de différents domaines et parlé avec des professeurs, et je commence à penser que c'est une mauvaise approche. J'ai lu qu'il était utile de trouver un problème...
En 1937, Turing décrit une machine de Turing. Depuis lors, de nombreux modèles de calcul ont été décrits dans le but de trouver un modèle ressemblant à un vrai ordinateur, mais suffisamment simple pour concevoir et analyser des algorithmes. En conséquence, nous avons une douzaine d'algorithmes...
Je suis un étudiant de 2e année en théorie. Je travaille sur un problème depuis un an (en théorie des graphes / algorithmes). Jusqu'à hier, je pensais que j'allais bien (j'étendais un théorème à partir d'un papier). Aujourd'hui, j'ai réalisé que j'avais commis une simple erreur. J'ai réalisé qu'il...
Le domaine de l'informatique distribuée a été terriblement mis de côté pour développer une seule théorie mathématique décrivant les algorithmes distribués. Il existe plusieurs «modèles» et cadres de calcul distribué qui ne sont tout simplement pas compatibles les uns avec les autres. L’explosion...
C'est une question liée à celle-ci . En le reformulant sous une forme beaucoup plus simple après de nombreuses discussions, la question semblait totalement différente. La preuve classique de l’indécidabilité du problème posé consiste à démontrer une contradiction lorsqu’on essaie d’appliquer à...
J'aimerais comprendre Applicativeen termes de théorie des catégories. La documentation de ce documentApplicative indique qu’il s’agit d’ un foncteur fort monoïdal laxiste . Premièrement, la page Wikipedia sur les foncteurs monoïdaux indique qu’un foncteur monoïdal est laxiste ou fort . Il me semble...
Ma question est simple: Quel est le temps d'exécution le plus défavorable du meilleur algorithme connu pour calculer une composition simple d'une matrice ?n × nn×nn \times n Eigendecomposition réduit-il à la multiplication matricielle ou les algorithmes les plus connus (via SVD ) sont-ils dans le...
Contexte Le calcul sur des nombres réels est plus compliqué que celui sur des nombres naturels, puisque les nombres réels sont des objets infinis et qu'il existe un nombre incalculable de nombres réels. Par conséquent, les nombres réels ne peuvent être fidèlement représentés par des chaînes finies...
C'est une question sur la complexité du circuit. (Les définitions sont en bas.) Yao et Beigel-Tarui ont montré que chaque famille de circuits de taille possède une famille de circuits équivalente de taille de profondeur deux , où la porte de sortie est une fonction symétrique et le deuxième niveau...
Le problème de l’isomorphisme graphique (IG) est sans doute le candidat le mieux connu pour un problème NP-intermédiaire . L'algorithme le plus connu est l'algorithme sous-exponentiel avec la durée d'exécution . On sait que GI n’est pas complet sauf si la hiérarchie polynomiale...