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
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...
Dans la multiplication matricielle de Strassen, nous affirmons un fait étrange (du moins pour moi) que la multiplication matricielle de deux 2 x 2 prend 7 multiplications. Question: Comment prouver qu'il est impossible de multiplier deux matrices 2 x 2 en 6 multiplications? Veuillez noter que les...
Dans l'étude Complexity of the Frobenius Problem de Ramírez-Alfonsín, un problème s'est révélé être NP-complet en utilisant les réductions de Turing. Est-ce possible? De quelle façon précisément? Je pensais que cela n'était possible que par une réduction polynomiale de plusieurs fois. Y a-t-il des...
Il y a une réduction dans le livre de Sipser "Introduction à la théorie du calcul" à la page 286 de 3SAT au problème de chemin hamiltonien. Y a-t-il une réduction plus simple? Par plus simple, je veux dire une réduction qui serait plus facile à comprendre (pour les étudiants). Y a-t-il une...
Dans Algorithmics for Hard Problems de Hromkovič (2e édition), il y a ce théorème (2.3.3.3, page 117): Il existe un problème de décision (décidable) tel que pour chaque algorithme qui résout il existe un autre algorithme qui résout également et remplit en outreA P A ′ PPPPUNEAAPPPUNE′A′A'PPP ∀∞n ∈...
J'étudie la complexité informatique et je me demandais pourquoi les problèmes NP-Complete (NPC) sont une classe importante. Je trouve évident pourquoi nous voulons montrer qu'un problème de NP donné est NP-difficile. Je comprends également la définition de NPC, et que montrer un problème de...
Faut-il qu'un problème NP-hard soit calculable? Je ne pense pas, mais je ne suis pas
Mon objectif est de résoudre le problème suivant, que j'ai décrit par son entrée et sa sortie: Contribution: Un graphe acyclique dirigé avec m nœuds, n sources et 1 puits ( m > n ≥ 1 ).ggGmmmnnn111m > n ≥ 1m>n≥1m > n \geq 1 Production: Le VC-dimension (ou une approximation de celui - ci)...
Pour chaque fonction calculable existe-t-il un problème qui peut être résolu au mieux en temps ou existe-t-il une fonction calculable telle que chaque problème qui peut être résolu dans peut également résolu en temps ?Θ ( f ( n ) ) f O ( f ( n ) ) o ( f ( n ) )FFfΘ ( f( n ) )Θ(F(n))\Theta(f(n))FFfO...
Je cherche des exemples de problèmes qui ont une borne inférieure de Ω(|x|2Ω(|x|2\Omega(|x|^2 ) pour l'entrée xxx . Le problème doit avoir les propriétés suivantes: Ω(n2)Ω(n2)\Omega(n^2)Preuve d'exécution Ω ( n 2 ) pour tout algorithme - la première priorité est d'avoir un argument de limite...
Partout, les manuels supposent que le problème de la correspondance de poste borné est NP-complet (pas plus de NNN index autorisés avec répétitions). Cependant, nulle part on ne montre une réduction du temps polynomiale simple (comme dans quelque chose qu'un étudiant peut comprendre) d'un autre...
Grâce au théorème de min-cut max-flow, nous savons que nous pouvons utiliser n'importe quel algorithme pour calculer un flux maximum dans un graphe de réseau pour calculer une -min-cut. Par conséquent, la complexité du calcul d'une coupe minimale n'est pas plus que la complexité du calcul d'un...
Je suis intéressé par une légère variante du carrelage, le puzzle: chaque bord d'une tuile (carrée) est étiqueté avec un symbole de , et deux tuiles peuvent être placées l'une à côté de l'autre si le symbole sur le bord opposé d'une tuile est et le symbole sur le bord opposé de l'autre tuile est ,...
La théorie existentielle des réels est dans PSPACE , mais je ne sais pas si elle est PSPACE-Complete . Si je crois que ce n'est pas le cas, comment pourrais-je le prouver? Plus généralement, étant donné un problème dans une classe de complexité X , comment puis-je montrer qu'il n'est pas X-Complete...
Comme suit de ma question précédente , j'ai joué avec l' hypothèse de Riemann comme une question de mathématiques récréatives. Dans le processus, je suis arrivé à une récurrence assez intéressante, et je suis curieux de son nom, de ses réductions et de son aptitude à la solvabilité de l'écart entre...
Wikipédia le définit comme Un algorithme est dit de temps polynomial si son temps de fonctionnement est délimité par une expression polynomiale dans la taille de l'entrée pour l'algorithme, c'est-à-dire pour une constante k.T( n ) = O ( nk)T(n)=O(nk)T(n) = O(n^k) L'algorithme fonctionne en temps...
J'ai lu quelque part que le plus algorithme efficace trouvé peut calculer les facteurs le temps, mais le code que j'ai écrit est O ( n ) ou éventuellement O ( n log n ) en fonction de la rapidité de la division et du module. Je suis sûr que j'ai mal compris quelque chose, mais je ne sais pas où....
Existe-t-il une technique générale pour prouver qu'un problème n'est PAS NP-Complete? J'ai reçu cette question à l'examen qui m'a demandé de montrer si un problème (voir ci-dessous) est NP-Complete. Je ne pouvais pas penser à une vraie solution, et je viens de prouver que c'était en P. Évidemment,...
Le théorème de Galois dit effectivement que l'on ne peut pas exprimer les racines d'un polynôme de degré> = 5 en utilisant des fonctions rationnelles de coefficients et de radicaux - ne peut-on lire pour dire que, étant donné un polynôme, il n'y a pas d'algorithme déterministe pour trouver les...