Lorsque j'expliquais la preuve de Baker-Gill-Solovay qu'il existe un oracle avec lequel nous pouvons avoir, , et un oracle avec lequel nous pouvons avoir à un ami, une question s'est posée pour savoir pourquoi de telles techniques sont mal adaptées pour prouver le problème , et je n'ai pas pu...
Le problème 3SUM essaie d'identifier 3 entiersa , b , cune,b,ca,b,cSSSnnna + b + c = 0une+b+c=0a + b + c = 0 On suppose qu'il n'y a pas de meilleure solution que quadratique, c'est-à-dire o ( n2)o(n2)\mathcal{o}(n^2)o (nlog( n ) + n2)o(nbûche(n)+n2)\mathcal{o}(n \log(n) + n^2) Je me demandais donc...
J'ai un ensemble de paires. Chaque paire est de la forme (x, y) telle que x, y appartiennent à des entiers de la plage [0,n). Donc, si le n est 4, alors j'ai les paires suivantes: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) J'ai déjà les paires. Maintenant, je dois construire une combinaison en utilisant...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Soit un ensemble de nombres naturels. Nous considérons sous l'ordre partiel de divisibilité, c'est-à-dire s_1 \ leq s_2 \ iff s_1 \ mid s_2 . LaisserS s 1 ≤ s 2SSSSSSs1≤s2⟺s1∣s2s1≤s2⟺s1∣s2s_1 \leq s_2 \iff s_1 \mid s_2 α(S)=max{|V|∣V⊆S,Vα(S)=max{|V|∣V⊆S,V\qquad \displaystyle \alpha(S) = \max \{|V|...
Étant donné une instance de SAT, je voudrais pouvoir estimer à quel point il sera difficile de résoudre l'instance. Une façon consiste à exécuter des solveurs existants, mais ce genre de résultat va à l'encontre du but d'estimer la difficulté. Une deuxième façon pourrait être de regarder le rapport...
Il est apparu à beaucoup que dans toutes les preuves de complétude que j'ai lues (dont je me souviens), il est toujours trivial de montrer qu'un problème se trouve dans , et de montrer qu'il s'agit de -hard est la partie ... difficile. Quels sont les problèmes compliqués par dont les vérificateurs...
Comme on le voit dans cette récente bande XKCD et ce récent article de blogde Peter Norvig (et une histoire de Slashdot mettant en vedette ce dernier), "regex golf" (qui pourrait mieux être appelé le problème de séparation des expressions régulières) est le casse-tête de définir l'expression...
Je prends un cours de complexité et j'ai du mal à trouver des réductions entre les problèmes de PNJ. Comment puis-je trouver des réductions entre les problèmes? Y a-t-il une astuce générale que je peux utiliser? Comment dois-je aborder un problème qui me demande de prouver qu'un problème est un...
Cette question a été inspirée par un commentaire sur StackOverflow . En plus de connaître les problèmes NP-complets du livre Garey Johnson, et bien d'autres; existe-t-il une règle empirique pour savoir si un problème ressemble à un problème NP-complet? Je ne cherche pas quelque chose de rigoureux,...
Énoncé informel du problème: Étant donné une chaîne, par exemple , nous voulons colorer certaines lettres rouges et certaines lettres bleues (et certaines pas du tout), de sorte que la lecture des lettres rouges de gauche à droite donne le même résultat que la lecture seules les lettres...
Il n'y a clairement aucun problème indécidable dans NP. Cependant, selon Wikipedia : NP est l'ensemble de tous les problèmes de décision pour lesquels les cas où la réponse est "oui" ont [.. des preuves qui sont] vérifiables en temps polynomial par une machine de Turing déterministe. [...] Un...
Je m'intéresse à la meilleure façon d'enseigner la complétude NP aux majors en informatique. En particulier, devrions-nous l'enseigner en utilisant des réductions Karp ou en utilisant des réductions Turing? Je pense que les concepts de complétude et de réduction de NP sont quelque chose que chaque...
Si quelqu'un devait construire un ordinateur quantique universel, cela aurait-il des implications sur le problème de P contre
En supposant que P NP, les problèmes NP-complets sont "difficiles à résoudre, mais ont des réponses faciles à vérifier". Est-il sensé de considérer le contraire, c'est-à-dire des problèmes pour lesquels il est facile de calculer une réponse correcte, mais difficile de vérifier une prétendue...
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 7 ans . Définition du problème Logical Min Cut (LMC) Supposons que est un digraphe non pondéré, et sont deux sommets de , et est accessible à partir de . Le problème...
Compte tenu de tout problème de calcul, la tâche de trouver des limites inférieures pour un tel calcul est-elle vraiment possible? Je suppose que cela se résume à la façon dont une seule étape de calcul est définie et quel modèle nous utilisons pour la preuve, mais étant donné que, prouvons-nous...
Soit une formule booléenne composée des opérateurs ET, OU et NON habituels et de certaines variables. Je voudrais compter le nombre de missions satisfaisant pour . Autrement dit, je veux trouver le nombre d'affectations différentes de valeurs de vérité aux variables de pour lesquelles suppose une...
L' analyse lissée a- t-elle trouvé son chemin dans l'analyse principale des algorithmes? Est-il courant que les concepteurs d'algorithmes appliquent une analyse lissée à leurs
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 7 ans . Je suis légèrement confus par une terminologie que j'ai rencontrée concernant la complexité des problèmes d'optimisation. Dans une classe d'algorithmes, j'ai...