J'ai récemment lu sur les algorithmes de vérification de la bisimilarité et lu que le problème est P-complet . En outre, une conséquence de cela est que ce problème, ou tout problème P-complet, est peu susceptible d'avoir des algorithmes parallèles efficaces. Quelle est l'intuition derrière cette...
Cette question a été migrée à partir de la bourse théorique de l'informatique, car elle peut être répondue sur la bourse de la science informatique. Migré il y a 7 ans . Dans cet article de Wikipédia sur le problème de la clique dans la théorie des graphes, il déclare au début que le problème de...
Je cherche des indices dans une question posée par mon moniteur. Je viens donc de comprendre que ce problème de décision est N P - c o m p l e t eNP-complete\sf{NP\text{-}complete} : Dans un graphe , y a-t-il un arbre couvrant dans qui contient un ensemble exact de S = { x 1 , x 2 , … , x n } comme...
Supposons que . \ mathsf {NPI} est la classe de problèmes dans \ mathsf {NP} qui ne sont ni dans \ mathsf {P} ni dans \ mathsf {NP} -hard. Vous pouvez trouver une liste des problèmes supposés être \ mathsf {NPI} ici .P≠NPP≠NP\mathsf{P} \neq
J'aimerais commencer la question en disant que je suis programmeur et que je n'ai pas beaucoup d'expérience en théorie de la complexité. Une chose que j'ai remarquée est que bien que de nombreux problèmes soient NP-complets, lorsqu'ils sont étendus à des problèmes d'optimisation, certains sont...
Une motivation possible pour étudier les classes de complexité de calcul est de comprendre la puissance de différents types de ressources de calcul (caractère aléatoire, non-déterminisme, effets quantiques, etc.). Si nous le regardons sous cet angle, il semble que nous pouvons obtenir un axiome...
Je comprends donc l'idée que le problème de décision est défini comme Existe-t-il un chemin P tel que le coût soit inférieur à C? et vous pouvez facilement vérifier que cela est vrai en vérifiant le chemin que vous recevez. Cependant, que se passe-t-il s'il n'y a pas de chemin qui correspond à ces...
Le problème de sous-ensemble est un problème classique NP-complet: Étant donné une liste de nombres et un cible , y a-t-il un sous-ensemble de nombres de qui se résume à ?LLLL kkkkLLLkkk Un étudiant m'a demandé si cette variante du problème appelé problème de "produit de sous-ensemble" est...
Voici le problème. Étant donné , où chaque . Existe-t-il un sous-ensemble dont la taille est au plus telle que pour tout ? J'essaie de réduire ce problème à SAT. Mon idée d'une solution serait d'avoir une variable pour chacun de 1 à . Pour chaque , créez une clause si . Ensuite et toutes ces...
Permettez-moi de commencer par noter qu'il s'agit d'un problème de devoirs, veuillez fournir uniquement des conseils et des observations connexes, AUCUNE RÉPONSE DIRECTE s'il vous plaît . Cela dit, voici le problème que je regarde: Soit HALF-CLIQUE = { | est un graphe non orienté ayant un...
Ceci est inspiré d'une question d'entrevue . On nous donne un tableau d'entiers et devons déterminer s'il existe des distincts tels que i < j < kune1, … , Unna1,…,ana_1, \dots, a_ni < j < ki<j<ki \lt j \lt k unek- unj= aj- unjeak−aj=aj−aia_k - a_j = a_j - a_i k - j = j - ik−j=j−ik...
C'est peut-être assez simple, mais j'ai du mal à obtenir cette réduction. Je veux réduire la somme des sous-ensembles à la partition, mais pour le moment je ne vois pas la relation! Est-il possible de réduire ce problème en utilisant une réduction Levin? Si vous ne comprenez pas, écrivez pour...
J'ai rencontré les doutes suivants sur la complexité des tours de Hanoi , sur lesquelles j'aimerais avoir vos commentaires. Est-ce en NP? Tentative de réponse: supposons que Peggy (prouveur) résout le problème et le soumette à Victor (vérificateur). Victor peut facilement voir que l'état final de...
Comment puis-je prouver que la conversion de CNF en DNF est NP-difficile? Je ne demande pas de réponse, juste quelques suggestions sur la façon de le
Souvent, si les complexités ont des constantes telles que 3n, nous négligeons cette constante et disons O (n) et non O (3n). Je n'arrive pas à comprendre comment pouvons-nous négliger ce triple changement? Une chose varie 3 fois plus rapidement qu'une autre! Pourquoi négligeons-nous ce fait?...
J'ai eu du mal à accepter la vue théorique de la complexité de "efficacement résolue par algorithme parallèle" qui est donnée par la classe NC : NC est la classe des problèmes qui peuvent être résolus par un algorithme parallèle dans le temps à p ( n ) ∈ S ( n k ) processeurs avec c , k ∈ N .O (...
Y a-t-il des problèmes dans qui ont des algorithmes randomisés dépassant les limites inférieures des algorithmes déterministes? Plus concrètement, connaissons-nous des pour lesquels ? Ici \ mathsf {PTIME} (f (n)) signifie l'ensemble des langages décidables par une MT aléatoire avec une erreur...
bbba c Nab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Je me demande dans quels groupes de complexité (par exemple pour les ordinateurs classiques et quantiques) il s'agit, et quelles approches (c'est-à-dire les algorithmes) sont les meilleures pour accomplir cette tâche. Le lien wikipedia ci-dessus ne...
Selon Immerman , la classe de complexité associée aux requêtes SQL est exactement la classe des requêtes sécurisées dans (requêtes de premier ordre plus opérateur de comptage): SQL capture les requêtes sécurisées. (En d'autres termes, toutes les requêtes SQL ont une complexité dans , et tous les...
Wikipedia indique que le problème de la somme des sous-ensembles consiste à trouver un sous-ensemble d'un multiset donné d'entiers, dont la somme est nulle. De plus, il déclare qu'il revient à trouver un sous-ensemble avec la somme sss pour tout sss donné . Je pense donc que comme ils sont...