J
Lawilog schrieb:
über genau das thema hab ich mir auch schon gedanken gemacht. und ich bin klar dafür, das das geht. es gibt keine rechenoperation die ncith umkehrbar ist. (auch wenn dabei mehrer lösungen möglich sind)
Das ist die falsche Frage: Es geht darum, ob sie effizient umkehrbar ist. Und das kann auf mit hoher Wahrscheinlichkeit negativ beantwortet werden:
Kennst Du 3SAT? Du hast ne Aussagenlogische Formel, die aus je 3 mit "Oder "Verknüpften Literalen besteht (den sogenannten Klauseln) und diese Klauseln sind dann mit "und" verknüpft. Jetzt ist die Frage, ob diese Formel erfüllbar ist.
Für jede der Klauseln ist das furchtbar einfach nachzuprüfen: Man kann direkt ne Belegung angeben, daß sie wahr wird. Der Haken: Die Frage, ob es möglich ist, daß alle gleichzeitig wahr werden ist dennoch NP-vollständig. Das heißt mit großer Wahrscheinlichkeit gibt es keinen polynomialen Algorithmus der dieses Problem lösen kann. Man geht davon aus, daß nur exponentielle Lösungen existieren... man grob gesprochen also nur durchprobieren kann.
MfG Jester