NP Vollständigkeit eines Problems beweisen

Hallo ich brauche Hilfe bei folgendem

Beispiel. Ich würde gerne beweisen,

dass das Problem NP vollständig ist.

Kann mir jemand helfen?

Gegeben sei ein Buch mit 114 Kapiteln.
Jedem Kapitel kann man beliebig viele

Verse hinzufügen.

Der "Wert" eines Kapitels ergibt sich

aus der Kapitelnummer plus Verszahl

des Kapitels.

Die Summe der Werte der Kapitel die

mehrmals vorkommen (also wenn zwei

oder mehrere Kapitel den selben Wert

haben) dividiert durch die Summe der

Werte der Kapitel die nur ein Mal

vorkommen soll auf 3 Nachkommastellen

genau 1,618 (goldener Schnitt)

ergeben.

Es müssen sowohl Kapitel vorkommen

deren Werte sich wiederholen als auch

welche deren Werte sich nicht

wiederholen.

Ich möchte nun den Rechenaufwand

berechnen und wie oben beschrieben

beweisen, dass dieses Problem NP-

vollständig ist.

Vielen Dank und liebe Grüsse

Entschuldigung übrigens für die Formatierung, habe es aus dem Editor kopiert und kann es als Gast leider nicht mehr ändern.

Liebe Grüsse

Schlangenmensch

Für die NP Vollständigkeit zeigt man, dass das Problem in NP ist und NP hart ist.

Die NP Härte zeigt man gerne über eine Reduktion auf ein Problem, von dem weiß, dass es NP Hart ist. Also via Defintion einer Funktion, die das Problem auf ein bekanntes NP Hartes Problem abbildet und in Polynomialzeit berechenbar ist.
Ich hätte es vlt. mal mit dem Rucksackproblem versucht.

Edit: Typing

Vielen Dank für deine Antwort.

P.S.: Sollte jemand mir einen vollständigen Beweis schreiben plus Komplexitätsberechung so wäre ich bereit 350€ zu bezahlen. Bei Interesse kann man mir schreiben unter Muhammed.Badr(at)gmx.net

Bei Erfolg würden "Folgeaufträge" kommen, da ich mehrere solche Probleme habe und es leider alleine nicht schaffe.

Vielleicht kann mir ja jemand helfen.

Und nein es ist nicht für eine Studienarbeit oder ähnliches, ich habe privates Interesse an diesen Problemen.

Liebe Grüsse

Gregor

Schlangenmensch schrieb:

Die NP Härte zeigt man gerne über eine Reduktion auf ein Problem, von dem weiß, dass es NP Hart ist.

Eher andersherum, heh? Du willst nicht zeigen, dass Du das Problem mit polynomiellem Mehraufwand lösen kannst, wenn Du dafür ein bekanntes, hartes Problem löst. Du willst zeigen, dass Du das harte Problem mit polynomiellem Mehraufwand lösen kannst, wenn Du das gegebene Problem löst.

Edit: @Threadersteller: Bist Du Dir sicher, dass das Problem NP vollständig ist? Zu dieser Aussage lässt man sich nämlich sehr schnell hinreißen, auch wenn das Problem letztendlich nur einem bekannten NP vollständigen Problem ähnelt.

Schlangenmensch

Gregor schrieb:

Schlangenmensch schrieb:

Die NP Härte zeigt man gerne über eine Reduktion auf ein Problem, von dem weiß, dass es NP Hart ist.

Eher andersherum, heh? Du willst nicht zeigen, dass Du das Problem mit polynomiellem Mehraufwand lösen kannst, wenn Du dafür ein bekanntes, hartes Problem löst. Du willst zeigen, dass Du das harte Problem mit polynomiellem Mehraufwand lösen kannst, wenn Du das gegebene Problem löst.

Hmm.. joa, klingt logisch. Was auch immer mir da beim schreiben gedacht habe.

@TE: Ich knobel zwar schon mal ganz gerne, aber Beweise lösen gegen Bezahlung, nein danke.

Gregor

Schlangenmensch schrieb:

Gregor schrieb:

Schlangenmensch schrieb:

Die NP Härte zeigt man gerne über eine Reduktion auf ein Problem, von dem weiß, dass es NP Hart ist.

Eher andersherum, heh? Du willst nicht zeigen, dass Du das Problem mit polynomiellem Mehraufwand lösen kannst, wenn Du dafür ein bekanntes, hartes Problem löst. Du willst zeigen, dass Du das harte Problem mit polynomiellem Mehraufwand lösen kannst, wenn Du das gegebene Problem löst.

Hmm.. joa, klingt logisch. Was auch immer mir da beim schreiben gedacht habe.

Ich muss zugeben, dass ich die Richtung da auch haeufig durcheinander bringe. Irgendwie ist das so eine Sache, die man sich immer wieder bewusst machen muss.

Ich verstehe das Problem nicht. Die folgende Lösung lässt sich in linearer Zeit berechnen:

Kapitel | Länge
1 | 8089
2 | 8088
3 | 3337
4 | 1
...
114 | 1

Es gibt halt überhaupt keine Eingabe bei dem Problem und deshalb ist es entweder trivial oder nicht lösbar.