Cette question est inspirée d'une question existante sur la possibilité de simuler une pile à l'aide de deux files d'attente en temps amorti par opération de pile. La réponse semble inconnue. Voici une question plus spécifique, correspondant au cas particulier dans lequel toutes les opérations PUSH...
CMSOL est la logique de deuxième ordre monadique, c'est-à-dire une logique de graphiques où le domaine est l'ensemble des sommets et des arêtes, il y a des prédicats pour la contiguïté des sommets et les incidences des arêtes et des sommets, il y a une quantification sur les arêtes, les sommets,...
Disons que nous découvrons des civilisations extraterrestres capables d'envoyer et de recevoir des messages à l'aide d'un canal de communication numérique interstellaire. (Par exemple, en utilisant des ondes radio modulées, des impulsions laser, en repositionnant des étoiles sur diverses orbites,...
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...
Nous pouvons considérer la complexité de Kolmogorov d'une chaîne xxx comme la longueur du programme le plus court PPP et saisir yyy tel que x=P(y)x=P(y)x = P(y) . Habituellement, ces programmes sont tirés d'un ensemble complet de Turing (comme PPP pourrait être la description d'une machine de...
Soit la taille minimale d'un circuit arithmétique (non monotone) calculant un polynôme multilinéaire et désignent la taille minimale d'un circuit booléen (non monotone) calculant la version booléenne de défini par:
L'entropie de Shannon est généralement utilisée pour prouver les résultats du codage de canal. Même pour les résultats de séparation source-canal, l'entropie shannon est utilisée. Étant donné l'équivalence entre les notions d'information de Shannon (global) et de Kolmogorov (local), y a-t-il eu une...
Considérez le problème de test d'appartenance au sous-groupe abelian suivant . Contributions: Un groupe abélien fini G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} avec arbitrairement grand .didid_i Un générateur de jeu d'un sous - groupe...
Le poidsd'une chaîne binaire est le nombre de uns dans la chaîne. Que se passe-t-il si nous sommes intéressés à calculer une fonction monotone sur des entrées avec quelques-unes?|x||x||x|x∈{0,1}nx∈{0,1}nx\in\{0,1\}^n On sait que décider si un graphe a une -clique est difficile pour les circuits...
Existe-t-il des problèmes décidables tels que pour aucun algorithme qui résout le problème, nous pouvons donner une limite de temps en fonction de la longueur n de l'instance d'entrée? Je suis arrivé à cette question parce que je pensais à ce qui suit: Supposons que nous ayons un problème...
Étant donné un graphe orienté avec n nœuds tels que chaque sommet a exactement deux bords sortants, et un nombre naturel N codé en binaire, deux sommets s et t, Je veux compter le nombre de chemins (pas nécessairement simples) de s à t dans N étapes. Est-ce un problème # P-difficile? Ou...
L'adversaire général de la borne inférieure est désormais connu pour caractériser la complexité des requêtes quantiques grâce aux travaux révolutionnaires de Reichardt et al. La même ligne de travail établit également des connexions avec le cadre du programme span pour concevoir des algorithmes...
ETH déclare que SAT ne peut pas être résolu dans le pire des cas en temps sous-exponentiel. Et le cas moyen? Y a-t-il des problèmes naturels dans le NP qui sont supposés être exponentiellement durs dans le cas moyen? Par cas moyen, on entend le temps de fonctionnement moyen avec une distribution...
Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné parXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk= Ak∪ Bk∪ Mk où UNEk= { aje∣ 1 ≤ i ≤ k...
Fixer un problème de recherche NP-complet, par exemple le formulaire de recherche de SAT. La recherche de Levin fournit un algorithme L pour résoudre X qui est optimal dans un certain sens. Plus précisément, l'algorithme est "Exécute tous les programmes P possibles en queue d'aronde sur l'entrée x...
Je partie d'une tentative de preuve . La tentative de preuve consiste en une réduction Karp du ⊕ P problème -complete ⊕ 3 RÉGULIER COUVERTURE vertex SAT.⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Étant donné un graphique cubique , la réduction produit une formule...
Il est bien connu que le problème d'arrêt n'est pas calculable. Cependant, il est possible de "compresser" exponentiellement des informations sur le problème d'arrêt, de sorte que sa décompression soit calculable. Plus précisément, il est possible de calculer à partir d'une description de machines...
aaabbbaaabbbaaabbbO(mlogmloglogm)O(mlogmloglogm)O(m\log m\log\log m)mmmmax{a,b}max{a,b}\max\{a,b\}Ω(mlogmloglogm)Ω(mlogmloglogm)\Omega(m\log m\log\log m) la limite inférieure de ce problème? Merci et salutations, et désolé si c'est une question aussi
Définissez comme la classe de langues pouvant être acceptée par une machine de Turing (multitape) dans le temps . (Le " " est juste pour simplifier la notation et éviter toute confusion.) Notez qu'il n'y a pas de autour de .f ( n ) + 1 + 1 O ( ⋅ ) f ( n ) + 1D T I M E (f( n )...
Quelle est la largeur d'arbre minimale d'un circuit sur pour calculer MAJ?{∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} Ici MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} sort 1 si au moins la moitié de ses entrées sont 111 . Je ne me soucie que de la taille du circuit (doit être polynomial) et...