Menge element Summe Optimierung leere Menge Teilmengen Menge M

Über NP

Von: , Frage gestellt am Mi, 9. Jun 2004

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

7 Antworten zu dieser Frage

1. Antwort von nach einer Stunde 1 hilfreich

   Re: Über NP

   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
   

2. Antwort von nach 13 Stunden 1 hilfreich

   Re: Über NP

   Hi,
   
   verallgemeinerung von Cheatah:
   
   1, 10, 100, 1000, 10000, ...
   
   zu jeder beliebigen Basis, oder anders gesagt
   
   m, m², m³, m⁴, m⁵, ...
   
   Hier ist was echt schwierigeres:
   
   http://en.wikipedia.org/wiki/EXPSPACE
   
   
   Gruß, Ralf
   

   • Antwort von nach 6 Tagen 0 hilfreich

     Re^2: Über NP

     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]
     

     • Antwort von nach 7 Tagen 0 hilfreich

       Re^3: Über NP

       Hi,
       verallgemeinerung von Cheatah:
       
       1, 10, 100, 1000, 10000, ...
       
       zu jeder beliebigen Basis, oder anders gesagt
       
       m, m², m³, m⁴, m⁵,
       ...
       
       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 2ⁿ-1 die kleinste Gesamtsumme. (Die zugehörige Menge ist M={2⁰, 2¹, ... ,2^n-1 } ) Dass mit einer kleineren Gesamtsumme das Problem nicht lösbar ist, lässt sich leicht zeigen. M besitzt 2ⁿ-1 Teilmengen, wenn man die leere Menge nicht mit rechnet. Wäre die Gesamtsumme aller Elemente von M kleiner als 2ⁿ-1 so wären auch die Elementsummen jeder Teilmenge von M kleiner als 2ⁿ-1. Wenn ich aber 2ⁿ-1 natürliche Zahlen habe, die alle kleiner als 2ⁿ-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
       

       • Antwort von nach 7 Tagen 0 hilfreich

         Re^4: Über NP

         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 2ⁿ-1. Und somit ist das schon die Menge mit der kleinsten Gesamtsumme. Um weniger als 2ⁿ-1 Zahlen auf 2ⁿ-1 Gesamtsummen zu verteilen, muß man Zahlen mehrfach vergeben. (nur um zu zeigen, daß ich es verstanden habe ;)
         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]
         

3. Antwort von nach 14 Stunden 0 hilfreich

   Re: Über NP

   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
   

   • Antwort von nach 6 Tagen 0 hilfreich

     Re^2: Über NP

     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
     

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!