Sudoku zur Kompression verwenden
-
Die Zuordnung Wert -> Hash(Wert) ist aber leider nicht bijektiv. Wie soll sie auch? Die Menge der unterschiedlichen Hashes ist kleiner als die Menge der unterschiedlichen Werte (es sei denn, du nimmst Hashes, die genauso groß sind wie die Werte, das ist dann aber auch keine Kompression).
-
yogle schrieb:
Sudoku zur Kompression verwenden, klingt interessant. Könnte man dabei (falls möglich) nicht auch mehrfach komprimieren?
Ich hatte mir auch mal zum Spaß überlegt, ob man Hashes zur Komprimierung verwenden könnte. So ein MD5-Hash ist in Byteform ja 16 Bytes lang. Angenommen, also wirklich nur rein fiktiv, man hätte eine Tabelle die alle möglichen Hashs von 20 Byte Strings enthält, dann würde man pro Hash 4 Bytes sparen. So eine ganze Datei durch und man hätte einige Bytes gespart. Aber jetzt könnte man ja diese Hashs wieder Hashen usw. usw... Zum Schluss hätte man eine gigabytegroße Datei zu 16 Bytes "komprimiert" und könnte diese dann wieder entkomprimieren.
Reines Gedankenspiel
Also ehrlich geasgt halte ich die Idee, Sudokus zur Kompression zu verwenden, für Unfug. Genauso wie die Idee mit den Hashes.
Hashes sind nicht eindeutig: Das heißt, dass Du sehr viele unterschiedliche Daten hast, die auf den gleichen Hashwert abgebildet werden. Entsprechend kannst Du aus den Hashwerten alleine nicht bestimmen, zu welchen Daten sie gehören. ...bzw. sie gehören einfach nicht zu bestimmten Daten.
Auch bei den Sudokus ist es so, dass Du den Informationsgehalt, der in den Daten steckt nicht einfach so auf Daten reduzieren kannst, die diesen Informationsgehalt nicht hergeben. Wenn deine Daten grundsätzlich schon so eine Art Sudoku-Struktur haben, wird das sicherlich gehen, das haben Daten im Allgemeinen aber nicht. Das heißt, dass Du Daten darüber abspeichern musst, wie Du deine zu komprimierenden Daten, auf diese Struktur bringst. ...und diese Daten werden dann wieder entsprechend groß sein: Vermutlich wird der Effekt deine zu speichernde Datenmenge sogar enorm vergrößern und nicht komprimieren. Übliche - verlustfreie - Kompressionsalgorithmen nutzen meistens Redundanzen und ähnliche Dinge in den ursprünglichen Daten aus, die dann irgendwie bei der Kompression entfernt werden. Mit anderen Worten: Da wird ausgenutzt, dass in den ursprünglichen Daten weniger Information enthalten ist, als man in dem genutzten Speicherplatz unterbringen könnte. Ich sehe keine Möglichkeit, wie man die grundsätzliche Tatsache, dass Informationen einen gewissen Speicherlatz benötigen, einfach so durch irgendein tolles Verfahren außer Kraft setzen kann.
Wenn man Gedankenspiele machen kann, bei denen rauskommt, dass man durch sein Verfahren alle Daten auf wenige Bytes reduzieren kann, dann ist das ein sicherer Hinweis darauf, dass das Verfahren einfach Mist ist. Es wird nicht funktionieren.
-
Was mir gerade ausffaellt: Sind die Spielfelder eigentlich immer symmetrisch voreingefuellt?
-
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 keinerBei 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.