Je suis certain que je ne suis pas le premier à entretenir l'idée que je vais présenter. Cependant, il serait utile que je puisse trouver de la documentation liée à l'idée. L'idée est de construire une machine de Turing M avec la propriété que si P = NP alors M résoudra 3-SAT en temps polynomial....
Comment montrer qu'une certaine propriété ne peut pas être exprimée en 2-CNF (2-SAT)? Existe-t-il des jeux, tels que des jeux de galets? Il semble que le jeu de galets noir classique et le jeu de galets noir et blanc ne conviennent pas à cela (ils sont complets sur PSPACE, selon Hertel et Pitassi,...
Soit une fonction booléenne de sensibilité s ( f ) et de sensibilité de bloc b s ( f ) .fffs(f)s(f)s(f)bs(f)bs(f)bs(f) La conjecture de conjecture de sensibilité Sensibilité-Bloc indique qu'il y a un tel que ∀ f , b s ( f ) ≤ s ( f ) c .c>0c>0c>0∀f, bs(f)≤s(f)c∀f, bs(f)≤s(f)c\forall f,\mbox{...
Soit une constante. Comment peut - on construire prouvablement un générateur pseudo - aléatoire que les fous -state automates finis?dréddrédd Ici, un automate fini state a nœuds, un nœud de début, un ensemble de nœuds représentant des états acceptés et deux bords dirigés étiquetés 0, 1 sortant de...
Je ne suis pas un informaticien théorique. Je suis un théoricien stable de l'homotopie utilisant -categories. J'ai vu des applications de la théorie des catégories et de la théorie des topos à l'informatique théorique, et je me demandais s'il y avait un moyen d'utiliser -catégories (et de...
Existe-t-il des exemples d'applications pratiques des jeux de parité, c'est-à-dire des systèmes, dans le monde réel, qui peuvent être représentés comme des jeux de parité? La documentation généralement associée sur les jeux de parité n'a presque jamais d'exemple pratique de cette...
J'ai essayé d'enrouler ma tête autour du quoi, pourquoi et comment du -calculus mais je ne suis pas parvenu à comprendre "pourquoi ça marche"?λλ\lambda «Intuitivement», j'obtiens le modèle de calculabilité de Turing Machines (TM). Mais cette -abstraction me laisse juste perplexe.λλ\lambda Supposons...
Dans l'article "Sur la complexité de certains jeux de coloriage", Bodlaender pose quelques questions ouvertes sur la complexité de décider si le joueur 1 ou 2 a une stratégie gagnante dans certains jeux de coloriage de graphiques. Est-ce que quelqu'un sait s'ils ont été résolus? 1) Dans une partie,...
La barrière des preuves naturelles de Razborov et Rudich déclare que sous des hypothèses cryptographiques crédibles, on ne peut pas espérer séparer NP de P / poly en trouvant des propriétés combinatoires de fonctions constructives, grandes et utiles. Il existe plusieurs résultats bien connus qui...
Existe-t-il des algorithmes de réorganisation des données à optimiser pour la compression? Je comprends que cela est spécifique aux données et à l'algorithme de compression, mais y a-t-il un mot pour ce sujet? Où puis-je trouver des recherches dans ce domaine? Plus précisément, j'ai une liste json...
Quels sont les problèmes avec les propriétés suivantes: 1) ils sont la restriction de problèmes (peut-être bien connus) qui sont PSPACE-complets; 2) les versions restreintes sont dans PSPACE, mais c'est un problème ouvert si elles sont complètes pour PSPACE (ou même si elles sont NP-hard). Quatre...
Je lis des sondages de Trevisan et Lovett sur les applications de la combinatoire additive en TCS. La majorité de ces applications relèvent de la complexité de calcul , par exemple, les limites inférieures. Je me demande si la combinatoire additive a également trouvé des applications dans la...
Pensez au modèle cellule-sonde. Existe-t-il une structure de données qui peut allouer des morceaux de mémoire contigus de n'importe quelle longueur (comme par exemple malloc en C), et les libérer, tout en évitant la segmentation de la mémoire, et exécute chaque opération dans le pire des cas O (log...
Je recherche une liste sur la complexité connue ou inconnue de divers problèmes théoriques / algébriques des nombres. Par exemple, GCD dans est ouvert,NC1NC1NC^1 l'affacturage en est ouvert,PPP le calcul de la cohomologie des faisceaux est -hard# P#P\#P , Arora et Barak indique qu'une variante de...
Il est connu que l'ajout d'une randomisation à erreurs bornées à PSPACE n'ajoute pas de puissance. Autrement dit, BPPSAPCE = PSPACE. On ne sait pas si P = BPP, mais on sait que .B PP⊆ Σ2∩ Π2BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Ainsi, il est possible (bien que supposé être faux) que l'ajout de...
Quelles sont les affirmations (peu connues) selon lesquelles, si elles sont vraies, le PH doit s'effondrer? Les réponses contenant une courte assertion de haut niveau avec des références sont appréciées. J'ai essayé de faire une recherche inversée sans trop de
Soit kkk fixé et GGG soit un graphe (connecté). Si je ne me trompe pas, il résulte des travaux de Bodlaender [1, Theorem 3.11] que si la largeur d'arbre de GGG est à peu près au moins 2k32k32k^3 , alors GGG contient une étoile K1,kK1,kK_{1,k} tant que mineur. Pouvons-nous rendre le terme 2k32k32k^3...
P/ poly= NP/ polyP/poly=NP/polyP/poly = NP/poly impliqueNP⊆ P/ polyNP⊆P/polyNP \subseteq P/poly , qui à son tour a des conséquences intéressantes comme l'effondrement de la hiérarchie polynomiale. Y a-t-il des implications intéressantes pour P/ poly≠ NP/ polyP/poly≠NP/polyP/poly \neq NP/poly...
Étant donné un graphe , nous devons trouver la cardinalité du plus grand ensemble de sommets afin que chacun d'eux soit présent dans chaque correspondance maximale possible.gGG Existe-t-il une solution à côté de l'évidence, supprimez chaque sommet et trouvez la correspondance maximale pour la voir...
en 1979 Hopcroft / Ullman a écrit que L ⊆ P ⊆ NP ⊆ PSpace est connu mais L ⊊ PSpace est le seul confinement approprié (et trivial) connu bien que tous soient supposés être des confinements appropriés, et "où les choses se tiennent encore" ~ 4 décennies plus tard . depuis lors, existe-t-il des liens...