SAT Tutorial

08/02/2008 - 19:02 von Thorsten Kiefer | Report spam
Hallo Leute,
ich schreibe gerade ein Tutorial zum SAT-Problem.
Ich würde mich über Kommentare und Beitràge freuen.

http://nillakaes.de/sattutorial/Sat...080207.pdf

Grüße
Thorsten
 

Lesen sie die antworten

#1 Philipp Zumstein
13/02/2008 - 13:36 | Warnen spam
Thorsten Kiefer schrieb:
ich schreibe gerade ein Tutorial zum SAT-Problem.
Ich würde mich über Kommentare und Beitràge freuen.


Ich versuche so höflich wie möglich ein paar Kommentare zu geben...


Bei Sàtzen wie

once I wanted to prove P=NP, and so I tried to
program a sat-solver with polynomial time complexity,



würde ich normalerweise aufhören weiterzulesen!



because others and I found out, that randomly
generated Sat instances are not that hard as those derived from know real hard
problems of NP, like e.g. factorization.



Wie hat man dies "herausgefunden"? Experimentell? Probleme in NP müssen
nicht schwer sein, zum Beispiel ist P in NP vollstàndig enthalten.
Polynomiell lösbare Probleme gelten i.A. als einfach. Wenn du NP-schwer
sagen willst, dann ist die Faktorisierung nicht ein gutes Beispiel, weil
man da nicht genau weiss wo es liegt.

Jetzt habe ich aufgehört richtig weiterzulesen.


Ich bin mir nicht sicher ob dieses Tutorial von irgendwelchem Nutzen
sein wird. Aber ich bin überzeugt, dass es *nicht* zur Lösung des
Problems "P=NP?" beitragen wird, wie du dies glaubst.

Grüsse,
Philipp

Ähnliche fragen