Sudoku zur Kompression verwenden
-
Klar, dass mit den Hashes ist ja auch nur ein Gedankenspiel.
Aber ich weiß nicht wie viele Kollisionen es unter 20 Bytesstrings gibt. Sicher es gibt einen Haufen Kollisionen bei denen die eine Datei 10 Bytes und die andere 4129458 Bytes groß ist, aber wenn beide genau 20 Bytes groß sind? Auch egal, umsetzen kanns eh keiner
Bei Sudoku kenn ich mich nicht so aus. Bin den Hype noch nicht erlegen
Gruß
yogle
-
yogle schrieb:
Klar, dass mit den Hashes ist ja auch nur ein Gedankenspiel.
Das machts nicht richtiger.
Aber ich weiß nicht wie viele Kollisionen es unter 20 Bytesstrings gibt. Sicher es gibt einen Haufen Kollisionen bei denen die eine Datei 10 Bytes und die andere 4129458 Bytes groß ist, aber wenn beide genau 20 Bytes groß sind? Auch egal, umsetzen kanns eh keiner
Häh? Ich kann dir so viel sagen: Es gibt immer so viele Kollisionen, dass du auf die selbe durchschnittliche Größe bei der Ausgabe kommst wie bei der Eingabe. Es kann nunmal kein Verfahren geben, dass alle Dateien verkleinert.
-
Gregor schrieb:
Die Frage ist doch, ob die Problemstellung, die man bei Sudoku hat, überhaupt in NP steckt. Es ist ja nicht so, dass kein Problem, das man irgendwie durch Suche oder ähnliches lösen kann, besser gelöst werden könnte.
Es ist wohl tatsächlich NP-vollständig. Daß es in NP steckt war hoffentlich vorher schon klar. Ein fertig ausgefülltes Feld zu prüfen geht schließlich sogar in Linearzeit.
Ich finde es auch nicht weiter erstaunlich, daß es NP vollständig sein soll, angesichts der Tatsache, daß schon deutlich "einfachere" Dinge, wie zum Beispiel Minesweeper NP vollständig sind.
-
Jester schrieb:
Gregor schrieb:
Die Frage ist doch, ob die Problemstellung, die man bei Sudoku hat, überhaupt in NP steckt. Es ist ja nicht so, dass kein Problem, das man irgendwie durch Suche oder ähnliches lösen kann, besser gelöst werden könnte.
Es ist wohl tatsächlich NP-vollständig. Daß es in NP steckt war hoffentlich vorher schon klar. Ein fertig ausgefülltes Feld zu prüfen geht schließlich sogar in Linearzeit.
Ist mir immer noch nicht klar, dass das in NP sein soll. Man hat da 81 Variablen. Ein Drittel davon ist meistens so in etwa vorgegeben. Für ein weiteres Drittel könnte ich aus dem Stand heraus entsprechende Gleichungen aufschreiben. Nämlich jeweils die Zeilensumme, die Spaltensumme und die Summe in jedem kleinen Quadrat. ...Das Lösen von Gleichungssystemen fällt AFAIK nicht in NP. Ok, aber man hat ja noch zu viele Freiheitsgrade. Ich weiß nicht, ob man da vielleicht noch die Ungleichungen reinbringen kann, die für jede Zeile, Spalte und jedes kleine Quadrat gelten? Keine Ahnung, ob man damit gut arbeiten kann. Zumindest bin ich mir alles andere als sicher, dass man dieses Problem nicht auf eine Art und Weise formulieren kann, wo es offensichtlich nicht in NP fällt.
Naja, vielleicht fehlt mir da aber auch einfach noch entsprechender theoretischer Hintergrund. Kannst Du mir erklären, warum Du denkst, dass dieses Problem NP ist?
PS: Ok, fällt natürlich in NP.
...die Frage ist aber eher: Gibt es auch eine "bessere" Komplexitätsklasse, in die dieses Problem auch fällt?
-
Ich vermute, Dir ist die NP-vollständigkeit unklar, nicht, ob es in NP liegt, oder?
Natürlich ist das 9x9 Sudoku nicht NP vollständig. Es gibt ja nur endlich viele Kombinationen. Durchprobieren geht also in O(1). Es geht natürlich um das allgemeine Sudoku-Problem: ein k*k x k*k - Feld, k in N, das entsprechend auszufüllen ist.
Ich habe jetzt auf die Schnelle nur ein paar Übungsblätter irgendwelcher Unis gefunden, wo man die NP-vollständigkeit beweisen sollte.
-
Jester: Ok, hast mich überzeugt.
...fast: Für das klassische Sudoku gilt nach einem dieser Aufgabenzettel:Eingeschränkt auf den Spezialfall k = 3 liegt das Problem SUDOKU in P.
-
Eingeschränkt auf den Spezialfall k = 3 liegt das Problem SUDOKU in P.
SUDOKU liegt sogar für den Spezialfall k beliebig aber fest in P. Die Lösung lässt sich mit einem Schritt berechnen wenn man das Eingabealphabet geschickt wählt. das gleiche gilt auch zB für Schach. Mit einer festen Eingabegröße kann man solche geschichten immer mit einem endlichen Automaten lösen, also in O(1) auf einer dtm ausrechnen.
Die NP-Vollständigkeit bei solchen Geschichten bezieht sich immer auf Spielbretter beliebiger größe.
-
Ok, ich seh es ein.
...vielleicht sollte ich mich mal ein bischen mit Komplexitätstheorie befassen.
-
Vielleicht mal ne Anmerkung am Rande:
Spektrum der Wissenschaft, März 2006 - Seite 100, "Sudoku oder die einsamen Zahlen"
Da werden auch Lösungsstrategien diskutiert.
-
Gregor schrieb:
Ist mir immer noch nicht klar, dass das in NP sein soll. Man hat da 81 Variablen. Ein Drittel davon ist meistens so in etwa vorgegeben. Für ein weiteres Drittel könnte ich aus dem Stand heraus entsprechende Gleichungen aufschreiben. Nämlich jeweils die Zeilensumme, die Spaltensumme und die Summe in jedem kleinen Quadrat. ...Das Lösen von Gleichungssystemen fällt AFAIK nicht in NP.
Ich glaub nicht, dass die Summe eine ausreichende Bedingung ist. In dem Fall könnte man das gesamte Sudoku nähmlich als System linearer Gleichungen schreiben mit 81 Variablen.
Um ein System mit 81 Variablen eindeutig lösen zu können braucht man mindestens 81 Gleichungen. Wir haben 9 Reihen, Spalten und Kisten. Das macht 27 Gleichungen. Wir brauchen also mindestens noch 54 weitere welche nur in Form von gegebenen Kästchen exsistiren können. Also ist 54 die Mindestanzahl von gegebenen Kästchen um ein eindeutig lösbares Sudoku zu haben. Laut Wikipedia gibt es aber auch eindeutig lösbare mit 17 gegeben Feldern.