Soit une formule 2CNF et k un entier non négatif. Il est prouvé dans cet article que le problème de décider si l'on peut supprimer au plus k clauses pour rendre satisfaisable, est un paramètre fixe traitable, où est le paramètre. Ma question est de savoir s'il existe des travaux qui généralisent ce...
A C0AC0AC^0 est la classe des circuits de taille polynomiale à profondeur constante avec portes NON et portes fan-in ET et OR sans limite, où les entrées et les portes ont également une fanout sans limite. Considérons maintenant une nouvelle classe, appelons-la A C0b fACbf0AC^0_{bf} qui est comme A...
Version rapide Existe-t-il des modèles de décohérence pour la marche quantique sur la ligne de sorte que nous pouvons régler la marche pour qu'elle se répande en pour tout ?1 / deux ≤ k ≤ 1Θ ( tk)Θ(tk)\Theta(t^k)1 / 2 ≤ k ≤ 11/2≤k≤11/2 \leq k \leq 1 Motivation Les marches aléatoires classiques sont...
Nous savons que si alors tout le PH s'effondre. Et si la hiérarchie polynomiale s'effondre partiellement? (Ou comment comprendre que le PH pourrait s'effondrer au-dessus d'un certain point et non en dessous?)P=NPP=NPP=NP En termes plus courts, quelles seraient les conséquences de et ?P ≠ N...
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...
Dans le chapitre 10 de HAC (10.4.2) , nous voyons le célèbre protocole d'identification Feige-Fiat-Shamir basé sur une preuve de connaissance nulle utilisant la difficulté (présumée) d'extraire des racines carrées modulo un composite difficile à factoriser. Je vais donner le schéma dans mes propres...
Le SAT unique est le problème bien connu: étant donné une formule CNF , est-il vrai que F a exactement un modèle?FFFFFF Je m'intéresse au problème «Exactement -SAT»: étant donné une formule CNF F et un entier m > 1 , est-il vrai que F a exactement m modèles?mmmFFFm>1m>1m>1FFFmmm Les deux...
Je me demande quelles sont les avancées récentes de la théorie des bases de données relationnelles et des domaines connexes? Je suis intéressé par les nouvelles approches, les langages de requête (alternatives à SQL et / ou extensions de celui-ci), les produits (propriétaires et open source, même...
Quels sont les problèmes standard à partir desquels nous pouvons réduire pour prouver les bornes inférieures ?Ω ( n logn )Ω(nlogn)\Omega(n\log n) Bien sûr, les problèmes d'état autres que le tri et la distinction des éléments.
Dans mon travail, le problème suivant se pose: Existe-t-il un algorithme connu, qui se rapproche du nombre chromatique d'un graphique sans un ensemble indépendant d'ordre 65? (Donc alpha (G) <= 64 est connu et | V | / 64 est une borne inférieure triviale, | V | une borne supérieure triviale....
J'ai trouvé un problème dans la preuve de réduction de sujet de Barendregt (Thm 4.2.5 des calculs Lambda avec types ). La dernière étape de la preuve (page 60), dit: "et donc par le lemme 4.1.19 (1), Γ,x:ρ⊢P:σ′Γ,x:ρ⊢P:σ′\quad\Gamma,x:\rho\vdash P:\sigma' . " Cependant, selon le lemme 4.1.19 (1), il...
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...
Comme cela est bien connu, les problèmes d'optimisation NP-hard peuvent avoir de nombreux rapports d'approximation différents, allant de la présence d'un PTAS à la non-approximation dans aucun facteur. Entre les deux, nous avons différentes constantes, , p o l y ( n ) , etc.O(logn)O(logn)O(\log...
Je recherche une langue L avec les propriétés suivantes: L ne doit pas être hors contexte. Le complément de L ne doit pas être hors contexte. (Tout ce que vous voyez dans les manuels comme exemples de langues non contextuelles semble ne pas répondre à cette deuxième exigence.) L ne devrait pas être...
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...
Étant donné un endofoncteur , nous pouvons définir les fonctions d'observation comme des fonctions polymorphes pour tout F -coalgebra, c'est-à-dire que obs est défini pour tout F -coalgebra \ langle A, c: A \ rightarrow FA \ rangle . obs: \ forall \ langle A, c \ rangle. A \ à B Une autre façon de...
Il est généralement plus simple de raisonner sur le calcul où la limitation est la finitude du calcul plutôt qu'un seuil comme "calculable en temps polynomial". Dans la théorie des langages formels par exemple, plutôt d'utiliser le ∃n.xn+1=xn∃n.xn+1=xn\exists n. x^{n+1} = x^n pour caractériser le...
Je veux juste connaître quelques exemples des fonctions qui peuvent être calculées par le calcul lambda non typé mais pas par des calculs lambda typés. Comme je suis un débutant, une réitération des informations de base serait appréciée. Merci. Edit: en tapant des calculs lambda, j'avais...
Disons que l'on a une langue , mais on ne sait pas quelles chaînes font réellement partie de la langue. Tout ce que l'on a est une vue finie du langage: un ensemble fini de chaînes qui sont connues pour être dans le langage, et un ensemble fini de chaînes qui sont connues ne pas être dans la...
Je recherche un algorithme rapide pour calculer le débit maximum dans les graphiques dynamiques. c'est-à-dire étant donné un graphe et nous avons le débit maximum dans de au . Ensuite, le nouveau / ancien nœud ajouté / supprimé avec ses bords correspondants pour former un graphique . Qu'est-ce...