La question suivante est liée à l'optimalité de l' algorithme de programmation dynamique Bellman-Ford - plus court (voir cet article pour une connexion). En outre, une réponse positive impliquerait que la taille minimale d'un programme de branchement non déterministe monotone pour le problème...
Dans un discours de Razborov, une curieuse petite déclaration est publiée. Si la FACTORISATION est difficile, alors le petit théorème de Fermat n'est pas prouvable dans .S12S21S_{2}^{1} Qu'est-ce que et pourquoi les preuves actuelles ne figurent-elles pas dans ?
Dans la complexité de la communication, la conjecture log-rank déclare que cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Où est la complexité de communication de M ( x , y ) et r k ( M ) est le rang de M (sous forme de matrice) sur les
Existe-t-il une classe naturelle de formules CNF - de préférence une qui a déjà été étudiée dans la littérature - avec les propriétés suivantes:CCC est un cas facile de SAT, comme par exemple Horn ou 2-CNF, c'est-à-dire que l'appartenance à C peut être testée en temps polynomial, et les formules F...
Considérons un langage non vide de chaînes binaires de longueur n . Je peux décrire L avec un circuit booléen C avec n entrées et une sortie telles que C ( w ) est vrai si w ∈ L : c'est bien connu.LLLnnnLLLCCCnnnC( w )C(w)C(w)w ∈ Lw∈Lw \in L Cependant, je veux représenter avec un circuit booléen C...
Il est connu que pour l' erreur , la pire définition de cas de complexité de communication aléatoire et la définition de cas moyenne sont équivalentes. Mais lorsque l'erreur est , la pire complexité de communication aléatoire est la même que la complexité de communication...
La minimisation des circuits est le problème pour minimiser la taille d'un circuit donné. Existe-t-il quelque chose de similaire pour les programmes généraux? En particulier, ma question est - Existe-t-il des algorithmes pour minimiser le nombre d'instructions pour un programme donné. Je sais que...
Je suis intéressé par le problème suivant. On nous donne en entrée une "permutation cible" , ainsi qu'une liste ordonnée d'indices . Ensuite, en commençant par la liste (c'est-à-dire la permutation d'identité), à chaque pas de temps nous l' dans avec le élément, avec probabilité indépendante . Soit...
L' hypothèse de Riemann vieille de plus d'un siècle et demi a des implications profondes en mathématiques et un grand édifice de la théorie mathématique est maintenant prouvé conditionnellement sur elle et de nombreuses variantes. Je suis récemment tombé sur une référence à un résultat conditionnel...
La complexité de la preuve est l'un des domaines les plus élémentaires de la théorie de la complexité informatique. Un objectif ultime de ce domaine est de prouver , c'est-à-dire que tout prouveur ne peut pas fournir une preuve d'insatisfiabilité d'une formule d'entrée donnée. NP≠ c o...
Suite aux questions équivalentes concernant NP-Completeness (voir la question de poids et la question dirigée ), je me demandais comment les problèmes paramétrés sont affectés par ces attributs. Quels problèmes de graphes durs sont W [ 1 ] -Dur sur les graphes dirigés, mais les paramètres fixes...
Quelle est la complexité du problème suivant ( P? NP-hard?):∈∈\in Entrée: un graphe acyclique dirigé , un ensemble d'arêtes arrières , et deux nœuds distincts et .E ′ ⊂ V × V s tD = ( V, E)D=(V,E)D=(V,E)E′⊂ V× VE′⊂V×VE'\subset V\times Vsssttt Question: Soit le graphe formé en ajoutant à les bords...
tttttt Θ ( journaln )Θ(Journaln)\Theta(\log n)tttΘ ( t + logt ⋅ logn )Θ(t+Journalt⋅Journaln)\Theta(t + \log t \cdot \log n) FFfFFfcccFFftttΩ ( t ⋅ ( c√- journaln ) )Ω(t⋅(c-Journaln))\Omega(t \cdot (\sqrt{c} - \log n)) Je ne connais aucun autre résultat général positif sur le problème de la...
Le théorème de Borsuk-Ulam dit que pour chaque fonction impaire continue ggg d'une sphère n dans un espace n euclidien, il y a un point X0x0x_0 tel que g( x0) = 0g(X0)=0g(x_0)=0 . Simmons et Su (2002) décrivent une méthode pour approximer le point X0X0x_0 utilisant le lemme de Tucker . Cependant,...
Considérez le problème suivant: Étant donné une matrice nous voulons optimiser le nombre d'additions dans l'algorithme de multiplication pour calculer v ↦ M v .MMMv ↦ Mvv↦Mvv \mapsto Mv Je trouve ce problème intéressant en raison de ses liens avec la complexité de la multiplication matricielle (ce...
Il est bien connu que certaines catégories de NP -Problèmes Ont dichotomie théorèmes, qui garantit que toutes les tâches de la classe est soit NP -complete ou est en P . Le résultat le plus connu est le théorème de dichotomie de Schaefer , ainsi qu'un certain nombre de généralisations. Je crois...
Le problème paramétré k-FLIP SAT est défini comme suit: Entrée: une formule 3-CNF avec n variables et une affectation de vérité \ sigma: [n] \ à \ {0,1 \} Paramètre: k Question: pouvons-nous transformer l'affectation \ sigma en une affectation satisfaisante \ sigma ' pour \ varphi retourner la...
Permettez à une machine de Turing probabiliste d'avoir accès à une pièce de monnaie injuste qui génère des probabilités (les flips sont indépendants). Définissez comme la classe de langages reconnaissable par une telle machine en temps polynomial. Il s'agit d'un exercice standard pour prouver que:B...
Supposons que j'ai un circuit booléen qui calcule une fonction f : { 0 , 1 } n → { 0 , 1 } . Supposons que le circuit est composé de portes ET, OU et NON avec au plus fan-in et fan-out 2.CCCF: { 0 , 1 }n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\} Soit une entrée donnée. Étant donné C et x , je...
QUESTION COURTE: MAJ-3CNF est-il un problème PP-complet avec plusieurs réductions? VERSION PLUS LONGUE: Il est bien connu que MAJSAT (décider si la majorité des affectations de phrase propositionnelle satisfont la phrase) est PP-complet sous plusieurs réductions et #SAT est # P-complet sous...