Wie die NP-Vollständigkeit für folgendes Problem lösen?

...komplette Frage anzeigen

2 Antworten

Gar nicht.

Dieses Problem liegt in P. (L= O(n²))

Moba1 30.06.2017, 08:16

Lieber Roderic, vielen Dank. Wenn du mir jetzt noch helfen könntest wie hoch der Rechenaufwand im konkreten Beispiel ist hättest du mir sehr geholfen. (Als Dankeschön würde ich dich übrigens auf einen Kaffee einladen oder so, per Überweisung). Liebe Grüsse

1
kreisfoermig 30.06.2017, 20:44
@Moba1

Bei deinem Problem handelt es sich um Folgendes:

Seien N:=100, a:=1,618 und b:=1,619. Sei d=3, so dass A:=10ᵈ·(1+a) sowie B:=10ᵈ·(1+b) ganzzahlig sind (wird später wichtig sein).

Jede Verteilung von Versen lässt sich als N-Tupel darstellen k ∈ INᴺ, wobei k[0] = #Verse in Kapitel 0, k[1] = #Verse in Kapitel 1, usw. Für i < N definiere Wert(k,i) := k[i] + i, der Wert von Kapitel i.

Für k ∈ INᴺ definiere Eind(k) := {i < N | Wert(k,i) ≠ Wert(k,j) für alle j < N mit j≠i}, die Menge der Kapitel mit eindeutigen Werten. Setze

e(k) := ∑ k[i] über i in Eind(k);
d(k) := ∑ k[i] über i < N nicht in Eind(k); und
S(k) := ∑k[i] für alle i < N.

Also gilt d(k) = S(k)–e(k). Und der Bruch, den wir untersuchen sollen, ist d(k)/e(k) = S(k)/e(k) – 1

Laut Beschreibung besteht dein Problem darin, die Menge L(a,b) ⊆ INᴺ von N-Tupel k zu bestimmen, so dass gilt:

a ≤ d(k)/e(k) < b.

Mit der o. s. Umformung ist dies zu 10ᵈ·(a+1)·e(k) ≤ 10ᵈ·S(k) < 10ᵈ·(b+1)·e(k) und damit zu

A·e(k) ≤ 10ᵈ·S(k) < B·e(k)

äquivalent. Beachte das all die Werte in diesem Ausdruck ganzzahlig sind. Zu prüfen ob dies gilt, ist offensichtlich polynimiell (sogar linear) in e(k) un S(k).

Die Größe, bzgl. deren wir letztlich berechnen müssen, ist die Summe der Werte in dem Tupel k, also S(k). Warum das? Weil ja dies auf konkrete Weise die natürlich Größe des Modells darstellt.

Es bleibt also zu zeigen, dass e(k) polynomiell berechnebar in S(k) ist.

Um e(k) zu berechnen geht man wie folgt (etwas ineffizient aber hinreichend) vor:

Sei e := 0. Und i := 0.
WÄHREND i < N (=100) MACHE:
Berechne u := k[i] + i.
Sei j := i+1 und setze p := falsch.
WÄHREND j < N und p = falsch MACHE:
Berechne v := k[j] + j.
Prüfe, ob v = u.
Wenn ja, dann setze p := wahr.
ENDE.
Wenn p = falsch, erhöhe e um 1.
ENDE.

Am Ende gilt e = e(k). Der Algorithmus kostet O(N²)·S(k) an Rechenschritten. Darum ist e(k) linear in S(k).

Darum ist das Problem L(a,b) in P.

Nun kommt es darauf an, welche Größe man den Variablen zuordnet, die die Modelle beschreiben, oder wie man die Parameter darstellen. Je nachdem, läuft der Algorithmus in quadratischer Zeit oder irgendwas. Jedenfalls ist es P-Time.

1
kreisfoermig 01.07.2017, 10:48
@kreisfoermig

Sorry, die Bezugsgröße sollte ja entweder N sein oder N+∑ k(i) über i<N sein. Bezogen auf N ist der Algorithmus O(N²). Bezogen auf n := N+∑ k(i) ist es O(N·n), also ein Hauch weniger als O(n²).

1
Moba1 03.07.2017, 06:35
@kreisfoermig

Ich bedanke mich herzlich. Auch für Sie gilt natürlich das Angebot mit dem Kaffee. Liebe Grüsse und danke noch ein Mal.

2

Wir haben 100 Kapitel
[0][5]  //Kapitelnummer, Verszahl
[1][9]  //Kapitelnummer, Verszahl
[2][25]  //Kapitelnummer, Verszahl
[3][25]  //Kapitelnummer, Verszahl
[4][25]  //Kapitelnummer, Verszahl
[99][..]

Ist das so gemeint?

2, 3, 4 haben den gleichen Wert.

Moba1 30.06.2017, 07:39

Nein, 2,3,4 hätten da unterschiedliche Werte der "Wert" den ich verwende aus Kapitelzahl plus Versanzahl des Kapitels besteht. Liebe Grüsse

0
safur 30.06.2017, 07:47
@Moba1

Ich verstehe es nicht :-)
Kann dir also nicht helfen.

0
kreisfoermig 01.07.2017, 10:39
@safur

Sei k das 100-Tupel (5,9,25,25,25,…).
Dann definiert man Wert(k,i) := k(i) + i.
Also

  i | Wert(k, i)
==================
0 | 5+0 = 5
1 | 9+1 = 10
2 | 25+2 = 27
3 | 25+3 = 28
4 | 25+4 = 29
. | .
. | .
. | .

Insbesondere haben Kapitel 2, 3 und 4 in deinem Modell nicht den gleichen Wert.

0

Was möchtest Du wissen?