www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLogikZwei offene Probleme gelöst?!
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Logik" - Zwei offene Probleme gelöst?!
Zwei offene Probleme gelöst?! < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Zwei offene Probleme gelöst?!: Link auf Download
Status: (Frage) beantwortet Status 
Datum: 02:03 Mi 03.10.2007
Autor: promath

Aufgabe
Ist das Primzahlproblem NP-vollständig?
Liegt das Graphenisomorphieproblem in P?  

Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: www.matheboard.de unter sonstiges

Komplexitätstheorie

1. Das Primzahlproblem ist NP-vollständig (Bit-Komplexität)
2. Das Graphenisomorphieproblem liegt in P

Damit liegen beide nicht in NP ohne NP vollständig und
P=NP wird wieder wahrscheinlicher.

Ich bin mir zwar bei beiden nicht unsicher, eine Lösung
gefunden zu haben, aber ganz sicher bin ich auch nicht.
Deshalb bleibe ich anonym und habe beide mal ins Netz gestellt:

http://promath.pr.ohost.de

        
Bezug
Zwei offene Probleme gelöst?!: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:19 Do 04.10.2007
Autor: felixf

Hallo!

> Ist das Primzahlproblem NP-vollständig?

Es liegt in P, wie schon seit laengerer Zeit bekannt ist. Google doch einfach mal nach []``PRIMES is in P''.

> Liegt das Graphenisomorphieproblem in P?

Ist es nicht auch NP-vollstaendig?

> 1. Das Primzahlproblem ist NP-vollständig
> (Bit-Komplexität)
>  2. Das Graphenisomorphieproblem liegt in P

Wenn auch nur eins davon stimmen sollte, waere bereits P = NP.

> http://promath.pr.ohost.de  

Ich habe nur kurz drueber geschaut, glaube aber nicht, dass es funktioniert. Wenn ich mal Zeit hab schau ich vielleicht mal genauer rein...

LG Felix


Bezug
        
Bezug
Zwei offene Probleme gelöst?!: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:52 Do 04.10.2007
Autor: dormant

Hi!

>  2. Das Graphenisomorphieproblem liegt in P

Du sollst noch zeigen, dass dein Algorithmus in polynomialer Zeit korrekt ausgeführt werden kann. Wenn du das schaffst wärest du um eine Million  $ reicher. Aber ich glaub nicht, dass so ein einfacher Beweis übersehen worden war.

Ich persönlich konnte deinen Algorithmus nicht nachvollziehen.

Gruß,
dormant

Bezug
        
Bezug
Zwei offene Probleme gelöst?!: Antwort
Status: (Antwort) fertig Status 
Datum: 23:32 Fr 05.10.2007
Autor: SEcki


> Ich bin mir zwar bei beiden nicht unsicher, eine Lösung
> gefunden zu haben, aber ganz sicher bin ich auch nicht.
> Deshalb bleibe ich anonym und habe beide mal ins Netz
> gestellt:

Soso, anonym? Warum das denn?

> http://promath.pr.ohost.de  

Also leicht war es nicht zu lesen, dein Gleichungssystem habe ich nicht ganz verstanden (das bracuht man aber auch nicht, um den Fehler zu sehen)

Nun gut - beide Beweise sind imo falsch. Also:

Prim ist NP vollständig: du reduzierst hier das Problem auf 3KNF - das ist aber trivial, da 3KNF ja NP vollständig ist. Das ist einfach die falsche Richtung - du musst eine belieibge Formel in konjunktiver Normalform in ein Primzahlproblem übersetzen. Das belisbt du schuldig.

Grapheniso ist in P: kurz gesagt: du schaust die die Knoten und alle Nachbarknoten mit deren Kantenzahl an. Du bleibst einen Beweis schuldig, dass 2 Graphen, die dort immer gleich sind, isomorph sind - das ist auch einfach falsch: nimm einen großen Kreis mit 10 Punkten und 2 kleine mit 5 - die sind nicht isomoprh wg. Zushkomponenten erfüllen aber deinen Algorithmus.

SEcki

Bezug
                
Bezug
Zwei offene Probleme gelöst?!: Dokumentation der Rückrichtung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:19 Sa 13.10.2007
Autor: promath

http://promath.pr.ohost.de
Eine genauere Dokumentation der Rückrichtung.

Bezug
                        
Bezug
Zwei offene Probleme gelöst?!: Ergänzung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:05 Sa 13.10.2007
Autor: promath

Ok,
ich weiss jetzt was an dem Graphenisomorphiebeweis
falsch ist. Ich zeige (a=>b) und (nicht b => nicht a).
Das gilt auch für a falsch und b wahr.
Und in diese Rubrik fällt das Gegenbeispiel.

Im Primzahlbeweis der Rückrichtung
ist die Reduktion von "Zahl hat Teiler der Länge n Bits"
auf "Zahl ist Primzahl" vermutlich verkehrt.
Aber vielleicht stimmt das erstere.


Bezug
                                
Bezug
Zwei offene Probleme gelöst?!: Primteilerproblem
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:33 Sa 13.10.2007
Autor: promath

In der Rückrichtung reduziere ich von KNF-SAT
auf "Zahl hat Teiler der Länge n Bits".
Wenn es stimmt, wäre zumindest das
Problem der Berechnung der Primteiler
NP-vollständig. PRIMES wäre erst dann
NP-vollständig, wenn eine Zahl berechnet
werden kann, die Primzahl ist, wenn die
zunächst berechnete Zahl einen Teiler der Länge n
Bits hat. Dieser letzte Schluss ist in der
Rückrichtung wohl verkehrt, aber vielleicht kann
man eine solche Zahl berechnen. Vielleicht auch
nicht, dann ist PRIMES in P aber die
Primfaktorzerlegung nicht.

Bezug
                                        
Bezug
Zwei offene Probleme gelöst?!: 1 verworfen - 1 eingeschränkt
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:29 Sa 13.10.2007
Autor: promath

Zusammenfassend ist bis jetzt zu sagen:  
eine Lösung ist definitiv falsch und
eine Behauptung wurde eingeschränkt,
das wurde jetzt auch auf der Homepage
vermerkt. P=NP wurde schonmal nicht
bewiesen, aber vielleicht ist das Problem
der Primfaktorzerlegung NP-vollständig, was
neu wäre. Vielleicht fällt mir oder euch
noch ein Fehler auf...

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]