Il existe de nombreuses applications de l'analyse réelle en informatique théorique, couvrant les tests de propriété, la complexité de la communication, l'apprentissage PAC et de nombreux autres domaines de recherche. Cependant, je ne peux penser à aucun résultat dans TCS qui repose sur une analyse...
Dans sa réponse à cette question , Stéphane Gimenez m'a signalé un algorithme de normalisation polynomiale en temps pour les preuves en logique linéaire. La preuve dans l'article de Girard utilise des réseaux de preuve, qui sont un aspect de la logique linéaire que je ne connais pas vraiment....
Je suis tombé sur un désaccord déroutant entre Agda et Coq qui n'est évidemment pas lié aux distinctions les plus connues entre leurs théories de types (par exemple, (im) prédicativité, induction-récursivité, etc.). En particulier, la définition suivante est acceptée par Agda: data Ty : Set0 ->...
Il y a une réputation, qu'en informatique, nous n'avons pas de livres de science populaire. Bien sûr, ce n'est pas vraiment vrai! (Dans le même esprit de la liste des livres que tout le monde devrait savoir? , Quels papiers devraient tous lire? , Quelles vidéos doivent surveiller de tout le monde?...
Je sais qu'il est indécidable de déterminer si un ensemble de tuiles peut carreler l'avion, un résultat de Berger utilisant des tuiles Wang . Ma question est de savoir s'il est également connu d'être indécidable pour déterminer si une seule tuile donnée peut carreler l'avion, un carrelage...
Je suppose que j'ai lu trop de documents ambitieux du CdRR . Le problème est que ces articles ne sont pas examinés par des pairs, mais semblent souvent intéressants et passent des contrôles de plausibilité de base. Ou peut-être pas, et j'ai juste besoin d'améliorer mes contrôles de plausibilité....
J'essaie de comprendre la relation entre l'isomorphisme des graphes et le problème des sous-groupes cachés. Y a-t-il une bonne référence pour
La conjecture des jeux uniques de Subhash Khot est l'un des domaines de recherche actifs en théorie de la complexité. Quelles preuves en avons-nous? Quelles preuves avons-nous contre cela?
Si j'ai un ensemble de contraintes linéaires dans lesquelles chaque contrainte a au plus (disons) 4 variables (toutes non négatives et avec {0,1} coefficients à l'exception d'une variable qui peut avoir un coefficient -1), que sait-on de la solution espace? Je suis moins préoccupé par une solution...
(J'ai posté cette question sur MathOverflow il y a deux semaines, mais jusqu'à présent sans réponse rigoureuse) J'ai une question sur les mesures de largeur de graphique des graphiques simples non dirigés. Il est bien connu que les cographes (graphes qui peuvent être construits par les opérations...
Message mis à jour le 31 août : j'ai ajouté un résumé des réponses actuelles sous la question d'origine. Merci pour toutes les réponses intéressantes! Bien sûr, tout le monde peut continuer à publier de nouvelles découvertes. Pour quelles familles de graphes existe-t-il un algorithme polynomial de...
Donné est un poignard. Vous souhaitez étiqueter chaque nœud en fonction du nombre de nœuds accessibles depuis celui-ci. est une borne supérieure triviale; Ω ( V + E ) est une borne inférieure (je pense). Existe-t-il un meilleur algorithme? Y a-t-il des raisons de croire que la borne inférieure peut...
Cette question est liée à une réponse que j'ai postée en réponse à une autre question. Le problème des 3 partitions est le problème suivant: Instance : entiers positifs a 1 ,…, a n , où n = 3 m et la somme des n entiers est égale à mB, de sorte que chacun a i satisfait B / 4 <a i <B / 2....
La largeur de l'arbre mesure la proximité d'un graphique avec un arbre. Il est difficile de calculer la largeur de l'arbre NP. L' algorithme d' approximation le plus connu atteint le facteur .O(logn−−−−√)O(logn)O(\sqrt{{\log}n}) Le théorème de Courcelle stipule que toute propriété de graphes...
Que sait-on de la complexité de trouver des circuits minimaux qui calculent SAT jusqu'à la longueur ? nnn Plus formellement: quelle est la complexité d'une fonction qui, étant donnée en entrée, sort un circuit minimal C tel que pour toute formule φ avec | φ | ≤ n , C ( φ ) = S A T ( φ )...
Dans l'enquête "Small Depth Quantum Circuits" de D. Bera, F. Green et S. Homer (p. 36 de ACM SIGACT News, juin 2007 vol. 38, no. 2) , j'ai lu la phrase suivante: La version classique de (dans laquelle les portes et ont un fanout au plus constant) est manifestement plus faible que . A N D O R A C 0Q...
La première étape de l'algorithme de test de primalité AKS consiste à vérifier si le numéro d'entrée est une puissance parfaite. Il semble que ce soit un fait bien connu de la théorie des nombres, car l'article ne l'explique pas en détail. Quelqu'un peut-il me dire comment faire cela en temps...
L'application la plus courante des types linéaires en PL est probablement de les utiliser pour donner des langages qui contrôlent l'alias (c'est-à-dire qu'une valeur linéaire a un seul pointeur vers elle, plus ou moins). Mais il y a un léger décalage entre cet usage et les modèles dénotatifs...
Pour A⊂[n]A⊂[n]A\subset [n] On note aiaia_i la ithithi^{th} plus petit élément de AAA . Pour deux ensembles d'éléments kkk , A,B⊂[n]A,B⊂[n]A,B\subset [n] , nous disons que A≤BA≤BA\le B si ai≤biai≤bia_i\le b_i pour chaque iii . A kkk -uniform hypergraphe H⊂[n]H⊂[n]{\mathcal H}\subset [n] est appelée...
Où puis-je trouver des graphiques relatifs à des problèmes réels? Je connais deux référentiels: Collection Sparse Matrix de l'Université de Floride Bodlaender's TreewidthLib