Pour un problème de recherche locale polynomiale , on sait qu'au moins une solution (optimum local) doit exister. Cependant, de nombreuses autres solutions pourraient exister, est-il difficile de compter le nombre de solutions pour un problème PLS complet? Je suis particulièrement intéressé par le...
Je lis le fameux article Impagliazzo et Wigderson en 1997. Comme je suis nouveau dans ce domaine et que l'article est une version concise de la conférence, j'ai du mal à suivre leurs épreuves. En particulier, certains de leurs nouveaux théorèmes manquent de preuves. À ma connaissance, aucune...
Supposons que l'on nous donne un tableau contenant des entiers non négatifs (pas nécessairement distincts).A[1..n]A[1..n]A[1..n] Soit un trié dans l'ordre non croissant. Nous voulons calculer A m = max i ∈ [ n ] B [ i ] + i .BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. La...
La classe UP est définie comme telle: La classe de problèmes de décision pouvant être résolus par une machine NP telle que Si la réponse est «oui», exactement un chemin de calcul est accepté. Si la réponse est «non», tous les chemins de calcul sont rejetés. J'essaie de développer l'intuition pour...
Le problème du "deuxième " est le problème de décider de l'existence d'une autre solution différente d'une solution donnée par exemple.XXX Pour certains problèmes -complets, la deuxième version de la solution est N P -complete (décidant de l'existence d'une autre solution pour le problème...
Impagliazzo, Paturi et Calabro, Impagliazzo, Paturi ont introduit l'hypothèse de temps exponentiel (ETH) et l'hypothèse de temps fortement exponentiel (SETH). En gros, SETH dit qu'il n'y a pas d'algorithme qui résout SAT dans le temps . 1,99n1.99n1.99^n Je me demandais ce que cela signifierait pour...
Je suis à la recherche d'une classe de complexité qui se rapporte à APX comme BPP se rapporte à P. J'ai déjà posé la même question ici , mais peut-être TCS serait un endroit plus fructueux pour les réponses. La raison de la question est que dans les problèmes pratiques, il faut souvent trouver des...
Après avoir lu une question connexe , sur les preuves d'existence d'algorithmes non constructives, je me demandais s'il existe des méthodes pour montrer l'existence de "petites" machines de calcul (disons, par état) sans les construire. Officiellement: supposons qu'on nous donne un langage et...
Crossposted de MO . Soit une classe de graphes définie par un nombre fini de sous-graphes induits interdits, tous cycliques (contenant au moins un cycle).CCC Existe-t-il des problèmes de graphes NP-difficiles qui peuvent être résolus en temps polynomial pour autre que Clique et Clique cover?CCC Si...
Cela m'embrouille. Un cas facile de comptage est lorsque le problème de décision est en et qu'il n'y a pas de solutions.PPP Une conférence montre que le problème du comptage du nombre de correspondances parfaites dans un graphique bipartite (de manière équivalente, le comptage du nombre de...
Considérez le problème suivant: Étant donné deux chaînes x, y, décidez s'il existe un homomorphisme de chaîne f tel que f (x) = y. Il est facile de montrer que ce problème est dans . Y a-t-il d'autres choses que nous pouvons dire sur ce problème? Par exemple, est-ce en , ou même en ?c o N P...
Comme nous le savons, la définition de la complexité de calcul de l'algorithme est presque sans controverse, mais la définition de la complexité de calcul des réels ou des modèles de calcul sur les réels n'est pas dans un tel cas. Nous connaissons le modèle et le modèle de Blum et Smales dans le...
Soit kkk un champ. Comme d'habitude, pour un f∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in k[x_{1},x_{2},\ldots,x_{n}] nous définissons L(f)L(f)L(f) comme la complexité linéaire de fff sur kkk . Soit FFF l'ensemble des monômes de fff , à savoir les monômes qui apparaissent en fff avec un coefficient non nul....
Supposons que notre entrée soit un binaire xxxet que nous sortir ⌊ x / c ⌋⌊x/c⌋⌊x/c⌋\lfloor x/c \rfloor , où ccc est un entier constant. Ce n'est qu'un changement si ccc est une puissance de deux, mais qu'en est-il des autres nombres? Pouvons-nous le faire avec un circuit à profondeur constante...
Considérez les jeux combinatoires à deux joueurs à informations complètes qui se terminent après un nombre polynomial de mouvements, et d'une manière alternée, les joueurs choisissent parmi un nombre fini de mouvements autorisés. La question habituelle est de savoir à quel point il est difficile de...
Le problème d'isomorphisme semi - groupe inverse fini est -il GI-complet ? Ici, les semi-groupes inverses finis sont supposés être donnés par leurs tables de
Un arbre de décision à lecture unique est défini comme suit: et F a l s e sont des arbres de décision à lecture unique.Tr u eTrueTrueFa l s eFalseFalse Si et B sont des arbres de décision à lecture unique et que x est une variable n'apparaissant pas dans A et B , alors ( x ∧ A ) ∨ ( ˉ x ∧ B ) est...
Je pensais à quelle classe ce langage appartient: est un graphique, est un nombre naturel et est le nombre chromatique dek k G }L = { ⟨ G , k ⟩ | GL={⟨g,k⟩∣gL =\{ \langle G,k \rangle \mid G kkkkkkG }g}G\} J'ai pensé à comme (1) "il n'y a pas de coloration des couleurs k-1" et (2) "il y a coloration...
Il y a la théorie algorithmique des graphes / théorie des nombres / combinatoire / théorie de l'information / théorie des jeux. Existe-t-il une analyse mathématique algorithmique? Selon wiki, l'analyse mathématique comprend les théories de la différenciation, de l'intégration, de la mesure, des...
En bref, la question est: dans quelle mesure, la capacité de calcul pour les tâches difficiles vous aide vraiment à résoudre des tâches faciles. (Il pourrait y avoir plusieurs façons de rendre cette question intéressante et non triviale, et voici une telle tentative.) Question 1: Considérons un...