Cette question s'est posée dans mon esprit après avoir lu les contributions d'András Salamon et Colin McQuillan à ma question précédente Compter les solutions des formules Monotone-2CNF . EDIT 30 e mars 2011 question n ° 2. Ajouté EDIT 29 e octobre 2010 Question reformulée après proposition András...
Soit une permutation. Notez que tandis que agit sur un domaine infini, sa description peut être finie. Par description , je veux dire un programme qui décrit les fonctionnalités de . (Comme dans la complexité de Kolmogorov.) Voir les explications ci-dessous. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi...
La résolution est un schéma pour prouver l'insatisfiabilité des CNF. Une preuve en résolution est une déduction logique de la clause vide pour les clauses initiales du CNF. En particulier, toute clause initiale peut être déduite, et de deux clauses A∨xA∨xA \lor x et la clause peut également être...
Contexte La complexité du circuit est définie comme l'ensemble des familles de circuits (c'est-à-dire des séquences de circuits, une pour chaque taille d'entrée) de profondeur bornée et de taille polynomiale construites à l'aide de fan-in illimités ET, OU et NON.AC0AC0AC^0 La fonction de parité...
Dans cette question , il a été mentionné qu'il existe des versions de complexité descriptive du théorème de Rice. J'ai trouvé une preuve du théorème suivant: Étant donné une classe de complexité C , les propriétés non triviales des langages en C ne peuvent pas être calculées en C J'avais déjà posté...
Étant donné un circuit booléen sur variables (qui utilise uniquement les portes NON, ET et OU), quelle est la manière la plus efficace d'extraire la formule booléenne représentée par le circuit? Existe-t-il un algorithme de polytime pour ce
Je parcourais le papier séminal de Les Valiant et j'ai eu du mal avec la proposition 4.3 à la page 10 du papier. Je ne vois pas pourquoi est-ce que s'il y a un générateur avec certaines valeurs pour avec une base , alors il existe un générateur avec les mêmes valeurs pour tout base ( ) ou ( ) pour...
Je jouais avec la question très intéressante et toujours ouverte " Alphabet of single-tape Turing machine " (par Emanuele Viola) et j'ai trouvé la langue suivante: L = { x ∈ { 0 , 1 }n st | x | = n = 2m et c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1
En un mot, les théorèmes de la hiérarchie du temps disent qu'une machine de Turing peut résoudre plus de problèmes si elle a plus de temps pour le calcul. En détail pour TM déterministe et fonctions constructibles dans le temps avec c'est et pour TM non déterministe et fonctions constructibles dans...
Un programme span est une manière linéaire-algébrique de spécifier une fonction booléenne présentée ici . Récemment, ce modèle a été utilisé pour montrer que la méthode de l'adversaire négatif fournit une caractérisation étroite (au moins jusqu'à ) de la complexité des requêtes quantiques.Journaln...
Pour répondre "quels problèmes peuvent être résolus par l'informatique", nous avons développé la théorie de la calculabilité. Pour les problèmes qui sont calculables, existe-t-il une théorie pour répondre à la question "est-ce que le programme est le plus simple"? Je ne pense pas que la complexité...
Nous savons que le logarithme du rang d'une matrice 0-1 est la borne inférieure de la complexité de communication déterministe, et le logarithme du rang approximatif est la borne inférieure de la complexité de communication aléatoire. Le plus grand écart entre la complexité de la communication...
Bien que les séparations exponentielles entre la complexité des requêtes quantiques à erreurs limitées ( ) et la complexité des requêtes déterministes ( D ( f ) ) ou la complexité des requêtes randomisées à erreurs limitées ( R ( f ) ) soient connues, elles ne s'appliquent qu'à certaines fonctions...
Une formule CNF monotone avec m termes sur n variables ( X1, … , Xnx1,…,xnx_1,\ldots,x_n ) est une formule de la forme , où chaque est un OU d'un sous-ensemble du les variables et vont de à .C i x 1 , … , x n i 1 mF( x1, … , Xn) = ⋀ CjeF(X1,…,Xn)=⋀Cjef(x_1,\ldots,x_n) = \bigwedge C_iCjeCjeC_iX1, …...
Ma question porte sur l'équivalence de la sécurité des différentes fonctions unidirectionnelles candidates qui peuvent être construites en fonction de la dureté de l'affacturage. En supposant que le problème de FACTEUR: [Étant donné pour des nombres premiers aléatoires P , Q < 2 n , trouver P ,...
Contexte: Nous considérons uniquement les digraphes. Soit CYCLE le langage des graphes avec un cycle; c'est un problème NL-complet. Soit HASEDGE le langage des graphiques avec au moins un bord. Ensuite, trivialement, n'est plus NL-hard, tandis que reste.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup...
La matrice de Moore est similaire à la matrice de Vandermonde mais a une définition légèrement modifiée. http://en.wikipedia.org/wiki/Moore_matrix Quelle est la complexité du calcul du déterminant d'une matrice de Moore de rang complet modulo un entier?n×nn×nn \times n Le déterminant de Moore...
Pour un graphe non orienté et un ensemble de sommets, ce qui est l'algorithme connu asymptotiquement le plus rapide pour trouver un chemin simple contenant tous les éléments de . Et si nous voulons que le chemin soit le plus court possible?S
Est-ce que implique
Ma question est pourquoi les bornes inférieures pour les circuits booléens de profondeur 3 avec les portes "et" et "xor" pour le déterminant n'impliquent pas les mêmes bornes inférieures pour les circuits arithmétiques sur ?ZZ\mathbb{Z} Quel est le problème avec l'argument suivant: Soit un...