Utilisé pour les questions sur les preuves existantes ou possibles d'un théorème ou d'une conjecture spécifique
Désolé pour le titre accrocheur. Je veux comprendre, que doit-on faire pour réfuter la thèse de Church-Turing? Quelque part j'ai lu c'est mathématiquement impossible de le faire! Pourquoi? Turing, Rosser, etc. ont utilisé différents termes pour distinguer entre "ce qui peut être calculé" et "ce qui...
Le but de cette question est de recueillir des exemples d'informatique théorique où l'utilisation systématique des ordinateurs était utile. dans la construction d'une conjecture qui mène à un théorème, falsifier une conjecture ou une approche par preuve, construire / vérifier (des parties de) une...
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,...
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 à...
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...
Nous savons que si vous avez une machine PSPACE, elle est suffisamment puissante pour donner une preuve interactive de la hiérarchie polynomiale à n’importe quel niveau. (Et si je me souviens bien, tout ce que vous avez besoin est #P.) Mais si vous voulez donner une preuve interactive de l'...
J'étais (et je suis toujours) vraiment intéressé par la réponse à cette question, car il s'agit d'une variation intéressante sur la complexité des jeux qui n'a pas été résolue, alors j'ai offert une prime. Je pensais que la question d'origine était très probablement trop difficile, alors j'ai posté...
Je m'intéresse de plus en plus à la théorie des graphes spectraux, que je trouve fascinante, et j'ai commencé à rassembler quelques documents que je n'ai pas encore lus plus attentivement que ce que j'ai jusqu'à présent. Cependant, je suis curieux d'une déclaration apparue dans plusieurs sources...
Existe-t-il des exemples de jouets qui fournissent des informations «essentielles» sur la compréhension des trois obstacles connus au problème P= NPP=NPP = NP - la relativisation, les preuves naturelles et
Je m'intéresse à des exemples de problèmes où un théorème qui n'a apparemment rien à voir avec la mécanique quantique / l'information (par exemple énonce quelque chose sur des objets purement classiques) peut néanmoins être prouvé en utilisant des outils quantiques. Une enquête Quantum Proofs for...
Il est bien connu que toute preuve résolvant la question P vs NP doit surmonter la relativisation , les preuves naturelles et les barrières d' algèbre . Le diagramme suivant partitionne "l'espace de preuve" en différentes régions. Par exemple, correspond à l'ensemble des preuves qui relativisent et...
Cela fait plus d'un an depuis sa rétractation et sa correction de janvier 2017. Y a-t-il des nouvelles? Sinon, est-ce normal que la validation prenne autant de temps? Je m'attendrais à ce qu'il retienne beaucoup d'attention Quelqu'un de remarquable a-t-il parlé pour soutenir / douter du résultat...
Je lisais " Est-ce que P par rapport à NP est officiellement indépendant? ", Mais je suis resté perplexe. Il est largement admis dans la théorie de la complexité que . Ma question est de savoir si ce n'est pas prouvable (disons dans ). (Supposons que nous découvrions seulement que est indépendant...
Le lemme de pompage pour les langues régulières peut être prouvé en considérant un automate à états finis qui reconnaît la langue étudiée, en choisissant une chaîne avec une longueur supérieure à son nombre d'états et en appliquant le principe du pigeonhole. Le lemme de pompage pour les langues...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Récemment, Watrous et al ont prouvé que QIP (3) = PSPACE un résultat remarquable. Ce fut pour moi un résultat surprenant pour le moins et cela m'a fait réfléchir ... Je me demandais si les ordinateurs quantiques pouvaient être simulés efficacement par les ordinateurs classiques. Serait-ce...
IP = PSPACE est répertorié comme l'exemple canonique d'un résultat non relativisant, et la preuve en est qu'il existe un oracle OOO tel que , tandis que {\ sf coNP} ^ O \ subseteq {\ sf PSPACE} ^ O pour tous oracles O .c o N P O ⊆ P S P A C E O OcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf...
Je pense qu'un théorème de hiérarchie des tailles pour la complexité des circuits peut être une percée majeure dans le domaine. Est-ce une approche intéressante de la séparation des classes? La motivation de la question est que nous devons dire il existe une fonction qui ne peut pas être calculée...
Il est bien connu que l'ensemble des langages ayant des systèmes de preuve interactifs à deux prouveurs, dans lesquels le vérificateur s'exécute en temps polynomial (MIP), est NEXP. Mais existe-t-il des limites connues sur la puissance de ces preuves interactives lorsque les prouveurs sont limités...
Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord...