P und NP < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 23:30 Mi 05.12.2007 | | Autor: | promath |
| Aufgabe | | Lässt sich K-SAT auf mehrfaches GGT reduzieren? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich hatte am 3.10. eine Reduktion von K-SAT auf das Primzahlproblem anonym vorgestellt, die aber nicht richtig war. Die Version von Mitte Oktober beschränkte sich auf eine Reduktion von K-SAT mit n Variablen auf "Zahl hat keinen Teiler der Länge n Bit" und scheint bis heute richtig zu sein. Den Verlauf der Rechnung gibt es unter http://promath.ohost.de
Man geht von einem K-SAT Problem mit n Variablen aus und
berechnet eine Zahl mit n*n Bits wie auf der Seite beschrieben mit
der Eigenschaft, dass sie einen Teiler der Länge n Bits hat, wenn
es eine erfüllende Belegung gibt.
Heute hatte ich folgende Idee:
Die sonstigen Teiler der berechneten Zahl sind maximal n Bits lang.
Man berechnet zu dieser Zahl ein K-SAT mit n-1 Variablen
genauso wie im Hinweg der Rechnung unter der Annahme, dass
ein Teiler n-1 Bits lang ist. Genauso verfährt man mit derselben
Zahl unter den Annahmen, dass die Teiler n-2, ..., 1 Bit lang sind.
Zu diesen K-SAT Probleme kann man wiederum Zahlen
mit (n-1)*(n-1), ..., 1*1 Bits Länge berechnen, die genau dann
einen Teiler der Länge n-1, ..., 1 Bits haben, wenn die anfangs
berechnete Zahl einen Teiler dieser Länge hat.
Nun untersucht man, ob die Zahl und die n-1 berechneten
Zahlen GGTs haben, auch mehrfach.
Wenn dies der Fall ist und die Teiler
die passende Länge (n-1, ..., 1 Bits) haben, ist der GGT Teiler
der anfangs berechneten Zahl. So erfährt man alle Teiler
der Zahl und ihre Häufigkeit. Man beachte, dass nicht nur die
Primfaktoren von dieser Vorgehensweise erwischt werden und
alle Teiler der Zahl nicht länger als n Bits sind oder
komplementär. Um mögliche n Bit lange Teiler zu finden
multipliziert man alle gefundenen Teiler paarweise miteinander
und dividiert die Zahl durch jedes dieser Produkte und die Teiler
der Länge n-1 selbst.
Wenn ein Resultat die Länge n Bits hat, hat die Zahl einen
Teiler der Länge n Bits und das anfängliche Problem
ist erfüllbar.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:50 Do 06.12.2007 | | Autor: | promath |
Die Teiler der n*n Bits langen Zahl sind
natürlich bis zu n*n/2 Bits lang.
Man berechnet die Zahlen bis zu dieser
Bitlänge und verfährt genauso.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:28 Mo 10.12.2007 | | Autor: | promath |
Hallo Leute,
die Behauptung ist natürlich Blödsinn.
Denn: es kann sein, dass die berechneten
Zahlen Vielfache voneinander sind!
Also nicht immer sofort posten...
Ich habe seit dem 3.10. immer mal wieder
nachts über das Problem nachgedacht.
Es scheint mir so, dass die Entscheidung
"Zahl hat Teiler der Länge n Bit"
komplexer ist als "Zahl ist Primzahl",
obwohl der naive Probieralgorithmus
schneller ist!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:28 Do 13.12.2007 | | Autor: | promath |
An diesem Beispiel sieht man schön den Kern der Beziehung von P und NP. Man kann zu einem K-SAT Problem mit n Variablen eine Zahl mit n*n Binärstellen berechnen, die genau dann einen Teiler der Länge n (n variable Stellen und eine 1 davor, also eigentlich der Länge n+1) hat, wenn das Problem erfüllbar ist. Das ist eigentlich nicht verwunderlich, weil es 2 hoch n Belegungen und genauso viele mögliche Teiler gibt. K-SAT liegt ist NP-vollständig. Das Primzahlproblem ist aber in P. Die spannende Frage ist: wird das Problem durch die weitere Hinzunahme von Teilern einfacher (P!=NP) oder nicht (P=NP). Man kann nicht so einfach eine Zahl berechnen, die Primzahl ist, wenn die andere Zahl einen Teiler der Länge n hat. Meine Rechnungen führten mich immer auf Mengen von Primzahlen exponentieller Größenordnungen. Ein Paradoxon. Gleichzeitig werden Teiler der Länge n vom polynomiellen AKS-Algorithmus in der Primzahlentscheidung erkannt, auch wenn es sonst keine weiteren Teiler gibt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Fr 21.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
