On sait qu'avec un ensemble dénombrable d'algorithmes (caractérisés par un nombre de Gödel), nous ne pouvons pas calculer (construire un algorithme binaire qui vérifie l'appartenance) tous les sous-ensembles de N. Une preuve pourrait être résumée comme suit: si nous le pouvions, alors l'ensemble de...
Soit une fonction booléenne et considérons f comme une fonction de à . Dans ce langage, l'expansion de Fourier de f est simplement l'expansion de f en termes de monômes libres carrés. (Ces monômes forment une base pour l'espace des fonctions réelles sur . La somme des carrés des coefficients est...
Je suis un débutant travaillant sur des méthodes prouvant l'équivalence d'un programme. J'ai lu quelques articles sur la définition de relations logiques ou de simulations pour prouver que deux programmes sont équivalents. Mais je suis assez confus au sujet de ces deux techniques. Je sais seulement...
Les méthodes polynomiales , par exemple Nullstellensatz combinatoire et le théorème de Chevalley-Warning sont des outils puissants en combinatoire additive. En représentant un problème avec des polynômes appropriés, ils peuvent garantir l'existence d'une solution ou le nombre de solutions aux...
La plupart (tous?) Des assistants de preuve ont des bugs de solidité corrigés à l'occasion. Cependant, parmi ceux que j'ai vus, ces bogues sont généralement difficiles à trouver involontairement, et les résultats prouvés avant que le bogue ne soit corrigé se maintiennent généralement après la...
Ceci est une question de suivi Quelle est la différence entre les preuves et les programmes (ou entre les propositions et les types)? Quel programme correspondrait à une preuve non constructive (classique) de la forme ∀ k T ( e , k ) ∨ ¬ ∀ k T ( e , k )∀k T(e,k)∨¬∀k T(e,k)\forall k \ T(e,k) \lor...
Les algorithmes classiques peuvent résoudre le 3-SAT en temps (randomisé) ou 1,3303 n temps (déterministe). (Référence: Best Upper Bounds on SAT )1,3071n1.3071n1.3071^n1.3303n1.3303n1.3303^n À titre de comparaison, l'utilisation de l'algorithme de Grover sur un ordinateur quantique rechercherait et...
Il est bien connu par le théorème de Ladner que si , alors il existe une infinité de problèmes -intermediate ( ). Il existe également des candidats naturels pour ce statut, tels que l'isomorphisme graphique, et un certain nombre d'autres, voir Problèmes entre P et NPC . Néanmoins, la grande...
Soit un problème (de décision) dans NP et soit # sa version de comptage.XXXXXX Dans quelles conditions sait-on que "X est NP-complet" "#X est # P-complet"?⟹⟹\implies Bien sûr, l'existence d'une réduction parcimonieuse est une de ces conditions, mais c'est évident et la seule de ces conditions que...
Le problème suivant est survenu lors de la recherche et il est étonnamment propre: Vous avez une source de pièces. Chaque pièce a un biais, à savoir une probabilité qu'elle tombe sur la "tête". Pour chaque pièce indépendamment, il y a une probabilité 2/3 qu'elle ait un biais d'au moins 0,9, et avec...
Un ordinateur doté d'un flux infini de bits vraiment aléatoires est plus puissant qu'un ordinateur sans un. La question est: est-elle suffisamment puissante pour résoudre le problème de l'arrêt? Autrement dit, un ordinateur probabiliste peut-il déterminer si un programme déterministe s'arrête ou...
Une chaîne a 2n2n2^n séquences, mais elles ne sont généralement pas toutes distinctes. Quelle est la complexité de trouver la fréquence maximale d'une sous-séquence? Par exemple, la chaîne "sous-séquence" contient 7 copies de la sous-séquence "sue" et c'est le maximum. Exemple de code de force...
J'ai entendu dire qu'il existe des arguments heuristiques en physique statistique qui donnent des résultats dans la théorie des probabilités pour lesquels des preuves rigoureuses sont inconnues ou très difficiles à obtenir. Quel est un simple exemple de jouet d'un tel phénomène? Ce serait bien si...
En une phrase: l'existence d'une hiérarchie pour impliquerait-elle des résultats de dérandomisation?BPTIMEBPTIME\mathsf{BPTIME} Une question connexe mais plus vague est: l'existence d'une hiérarchie pour implique-t-elle des limites inférieures difficiles? La résolution de ce problème heurte-t-elle...
On que car l'inverse impliquerait . Le théorème de Ladner établit que si alors . Cependant, la preuve ne semble pas généraliser à donc la possibilité ie semble ouvert.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne...
Il est facile de voir que l' isomorphisme graphique (GI) est en NP. C'est un problème ouvert majeur si l'IG est en coNP. Existe-t-il des candidats potentiels aux propriétés des graphiques qui peuvent être utilisés comme certificats IG de coNP? Des conjectures impliquant ? Quelles sont les...
Il y avait deux questions posées récemment sur cs.se qui étaient liées ou avaient un cas spécial équivalent à la question suivante: Supposons que vous ayez une séquence de n nombres tels que ∑ n i = 1 a i = n ( n + 1 ) . Décomposer en la somme de deux permutations, π et σ , de 1 … n , de sorte que...
Le récent résultat de la borne inférieure de la complexité du circuit de Ryan Williams fournit une technique de preuve qui utilise le résultat de la borne supérieure pour prouver la complexité des bornes inférieures. Suresh Venkat dans sa réponse à cette question, Y a-t-il des résultats...
Supposons que P = NP soit vrai. Y aurait-il alors une application pratique à la construction d'un ordinateur quantique, telle que la résolution plus rapide de certains problèmes, ou une telle amélioration serait-elle sans pertinence étant donné que P = NP est vrai? Comment caractériseriez-vous...
Le blog de Scott Aaronson a donné aujourd'hui une liste de problèmes / tâches ouverts intéressants en complexité. Un en particulier a retenu mon attention: Construisez une bibliothèque publique d'instances 3SAT, avec aussi peu de variables et de clauses que possible, qui aurait des conséquences...