Über NP

Wissenschaft Informatik
#1

Hallo,
ich bin durch Zufall auf ein Problem gekommen, das vielleicht schwerer als NP ist :
Gegeben sei n.
Finde eine Menge M mit n nat. Zahlen, so daß keine 2 Teilmengen die
gleiche Summe haben.

Ich denke, daß man so eine Menge erstmal raten muß -> nicht deterministisch.
Um dann die geratene Menge zu überprüfen, muß man alle Teilmengen überprüfen, was exponentiellen Aufwand hat. D.h. der Verifier läuft nicht mit polynomiellem sondern exponentiellem Aufwand.

Was haltet ihr davon ?
Kann der Verifier durch Optimierung vielleicht doch polynomiell ablaufen ?
Falls es mal Quantencomputer geben sollte, dann könnten man dieses Problem immernoch nicht effizient lösen, oder ?

Die Fragestellung ist ja ungefähr nach diesem Schema:
Nimm die Eingabe, bausche sie exponetiell auf und überprüfe die Rahmenbedingungen.
Ist diese Art von Fragestellung zur Kategorisierung in P/NP überhaupt geeignet, oder muß man da noch was beachten ?

Gruß
Thorsten

#2

Hi,

Finde eine Menge M mit n nat. Zahlen, so daß keine 2
Teilmengen die gleiche Summe haben.

M(1) := 1
M(i) := sum(M(1)…M(i-1))+1

Cheatah

#3

Hi,

verallgemeinerung von Cheatah:

1, 10, 100, 1000, 10000, …

zu jeder beliebigen Basis, oder anders gesagt

m, m2, m3, m4, m5, …

Hier ist was echt schwierigeres:

http://en.wikipedia.org/wiki/EXPSPACE

Gruß, Ralf

#4

Hallo,
nur zu den verbleibenden Fragen.

Falls es mal Quantencomputer geben sollte, dann könnten man
dieses Problem immernoch nicht effizient lösen, oder ?

Das ist selbst für NP-harte Probleme noch unklar.

Nimm die Eingabe, bausche sie exponetiell auf und überprüfe
die Rahmenbedingungen.
Ist diese Art von Fragestellung zur Kategorisierung in P/NP
überhaupt geeignet, oder muß man da noch was beachten ?

Im wesentlichen stimmt das. Die auf der Eingabe basierende Problemstellung weist vordergründig einen exponentiellen Suchraum auf.

Gruss
Enno

#5

Falls es mal Quantencomputer geben sollte, dann könnten man
dieses Problem immernoch nicht effizient lösen, oder ?

Das ist selbst für NP-harte Probleme noch unklar.

Warum ? OK, es ist unklar, wieviele QBits man verschränken kann,
aber wenn man mal von einer großen Anzahl n ausgeht, dann kann
man doch alle 2^n Möglichkeiten auf einmal durchrechnen.
Oder gibt’s da beim Quantencomputer noch andere Probleme ?

Thorsten

#6

Ok, dann nehmen wir doch die Menge mit der kleinsten Gesamtsumme.
Oder man gibt vor, daß die Menge eine vorgegebene Gesamtsumme haben
muß. Ich denke, die kann man so nicht generieren.

Gruß
Thorsten

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#7

Hi,

verallgemeinerung von Cheatah:

1, 10, 100, 1000, 10000, …

zu jeder beliebigen Basis, oder anders gesagt

m, m2, m3, m4, m5,
…

Hier ist was echt schwierigeres:

http://en.wikipedia.org/wiki/EXPSPACE

Gruß, Ralf

Ok, dann nehmen wir doch die Menge mit der kleinsten
Gesamtsumme.
Oder man gibt vor, daß die Menge eine vorgegebene Gesamtsumme
haben
muß. Ich denke, die kann man so nicht generieren.

Kann man doch! Wenn man annimmt, das 1 die kleinste natürliche Zahl ist, dann ist 2n-1 die kleinste Gesamtsumme. (Die zugehörige Menge ist M={20, 21, … ,2n-1 } ) Dass mit einer kleineren Gesamtsumme das Problem nicht lösbar ist, lässt sich leicht zeigen. M besitzt 2n-1 Teilmengen, wenn man die leere Menge nicht mit rechnet. Wäre die Gesamtsumme aller Elemente von M kleiner als 2n-1 so wären auch die Elementsummen jeder Teilmenge von M kleiner als 2n-1. Wenn ich aber 2n-1 natürliche Zahlen habe, die alle kleiner als 2n-1 sind, dann kommen automatisch auch Zahlen doppelt vor (Dirlichetsches Schubfächerprinzip)

also, ist das Problem, selbst mit der neuen Einschränkung, in linearer Zeit lösbar und damit sogar aus P.

grüße

unimportant

#8

Hallo,
ich verstehe. Wenn man von dieser Menge alle Teilmengen bildet, dann ergibt die Menge der Teilsummen vollständig(!) die Menge der natürlichen Zahlen von 1 bis 2n-1. Und somit ist das schon die Menge mit der kleinsten Gesamtsumme. Um weniger als 2n-1 Zahlen auf 2n-1 Gesamtsummen zu verteilen, muß man Zahlen mehrfach vergeben. (nur um zu zeigen, daß ich es verstanden habe :wink:
Danke, damit ist das Problem entschärft.

Um es mal aus anderer Sicht zu formulieren : Durch das exponentielle
„Aufbauschen“ der Eingabe entstehen so viele Constraints, so daß sie
direkt auf die Lösung zuführen.

Gruß
Thorsten

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]