Réduction simple (complétude NP)

Je cherche un moyen de prouver que le problème du plus court chemin de bicriteria est np complet. qui est, étant donné un graphique avec des longueurs et des poids, je dois savoir s'il existe un chemin dans le graphe de s à t avec une longueur totale < = L et poids < = W.Réduction simple (complétude NP)

Je sais que je dois prendre un problème complet NP et le réduire à celui-ci. Nous avons à notre disposition les problèmes suivants: 3-SAT, ensemble indépendant, couverture de vertex, cycle hamiltonien et adaptation en trois dimensions.

Des idées sur lesquelles peut-être viable?

merci

Source

2009-11-20 Allen

Vous pouvez vous arrêter aux heures d'ouverture de votre professeur. 1-1 temps avec les sciences informatiques PhD est une partie inestimable de votre éducation. Vous devriez en profiter pendant que vous le pouvez. –

Malheureusement, je n'ai pas ici ma copie de Garey et Johnson, et je ne me souviens pas de certains de ces problèmes. Si vous éditez votre question pour donner des définitions rapides, cela pourrait aider les gens à les trouver. (Exemple: 3-SAT: Étant donné un ensemble de variables booléennes, et un ensemble de clauses OU ensemble trois variables, dont certaines peuvent être annulées, pouvez-vous assigner des valeurs de vérité aux variables telles que toutes les clauses sont vraies?) –

Avez-vous essayé Google? 3ème coup est:

http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128_416/_article

L'article est pay-per-view, mais le cache Google fournit le bit importante dès le départ:

« Malheureusement, le cas multiobjectif (y compris le cas bicritère) est NP . -complete (3)

et les points de référence à:

(3) M. Garey et D. Johnson: Ordinateurs et indocilité: Guide de la théorie de NP-Complétude, New York: Freeman (1979)

qui est la référence standard pour les questions de cette forme. Alors, avez-vous regardé Garey et Johnson? Je n'ai pas de copie ici pour vérifier, mais c'était mon go-to quand j'ai fait des comps.

Source

2009-11-25 15:14:46 Eric

Chose est, ce que Garey et Johnson est vraiment utile pour cela est un recueil massif de problèmes NP-complets. Fréquemment, votre problème sera là (je suppose que le professeur aurait vérifié cela), et sinon c'est une grande source de problèmes pour essayer de réduire à ce que vous avez. Dans ce cas, l'étudiant obtient cinq problèmes à choisir, ce qui est déjà beaucoup plus facile à gérer que les centaines (littéralement) dans G & J. –

Parfois, G & J aidera avec un problème comme celui-ci en suggérant une chaîne de dérivation ... soit directement à l'un des problèmes les plus familiers, soit par un problème intermédiaire qui suggère une stratégie pour construire une preuve directe. – Eric

Répondre

Questions connexes