Posts by master_fluc

    Ich hätte gedacht, dass die Probleme, die in P sind, jedenfalls erlauben, den Suchraum auf eine polynomielle Anzahl von Lösungen zu begrenzen, und das in polynomieller Zeit (wichtig!). Sei es auch nur, dass der Algorithmus in polynomieller Zeit die richtige Lösung findet - das ist ja auch nur ein Spezialfall dieses Ansatzes.


    Der Suchraum muss aber nicht "begrenzt" werden (was auch immer du damit meinst), es kommt darauf an, dass der Algorithmus auch im Worst Case polynomiell in der Laufzeit beschränkt ist.
    Dass eine polynomielle Anzahl an potentiellen Lösungskandidaten maximal polynomielle Laufzeit zur Lösung erfordert, ist trivial.

    Verwechselst du da nicht Berechenbarkeit und Komplexität?


    Nein, aber jetzt weiß ich, wie du diesen Satz gemeint hast. Ich hatte in diesem Kontext nicht mit Berechenbarkeit gerechnet, sondern den Satz so verstanden, dass gemeint war, jeder Computer könnte eine nichtdeterministische Turing-Maschine simulieren und somit Probleme in polynomieller Zeit lösen.


    Eh nicht. Aber wenn es mir gelingen könnte zu beweisen, dass es keinen polynomiellen Algorithmus für ein bestimmtes NP-vollständiges Problem geben kann, wäre P=NP gelöst. Aber das habe ich nicht bewiesen.


    Dieser Negativ-Beweis ist allerdings schwer zu führen, aber solltest du es schaffen, ist dir die Million sicher.


    Wenn ich eine Aussage in eine andere Aussage umformen kann, wobei beide Aussagen zueinander logisch äquivalent sind, kann ich dennoch neue Erkenntnisse gewinnen. Also sind Tautologien nicht grundsätzlich nutzlos.


    Naja .. in diesem Kontext ist aber nicht viel damit gewonnen, wenn die Anzahl der Möglichkeiten, die der Algorithmus durchsuchen muss polynomiell ist, ist klar, dass dieser Algorithmus polynomielle Laufzeit hat. Interessant wird es dann, wenn die Anzahl der möglichen Lösungen exponentiell bleibt und der Lösungs-Algorithmus trotzdem polynomielle Laufzeit hat.
    Und genau darauf läuft die P=NP Problematik schlussendlich raus: Muss ich alle möglichen (exponentiell viele) Lösungen eine nach der anderen durchgehen (also exakte Enumeration als einzige Lösungsmethode), um das Problem zu lösen (dann P=/=NP) oder geht es nicht doch schneller (dann P=NP)?

    Solche Aussagen habe ich besonders gern. Mit einer solchen Aussage stellst du dich nämlich über mich und behauptest, dass du etwas Besseres bist, ohne aber darauf einzugehen, was konkret falsch ist. Man kann dir Glauben schenken oder auch nicht. In der Vergangenheit ist es in ähnlichen Fällen schon vorgekommen, dass derjenige, der Ähnliches behauptet hat, auf nähere Nachfrage nur einige wenige Punkte nennen konnte, die falsch waren, also die Aussage "der Text strotzt von Fehlern" eine maßlose Übertreibung war.


    Ich habe mich mit meinem Posting in keinster Weise "über dich gestellt" oder auch nur ansatzweise derartiges behauptet. Das Feedback bezog sich auch nicht auf dich, sondern auf deinen "Beweis". Wenn du da nicht unterscheiden und damit nicht umgehen kannst, ist das dein Problem.


    Dein "Beweis" ist Hand-Waving par excellence...


    Um dir auch ein paar Beispiele für Ungenauigkeiten, Halbwahrheiten und Fehlern in deinen Annahmen zu geben (alles aus einem einzigen Absatz - bei weitem kein Anspruch auf Vollständigkeit):

    Quote

    Die theoretische Grundlage hinter P und NP sind hierbei die so genannten Turing-Maschinen


    Dieser Satz ist schlicht falsch. Turing-Maschinen sind ein theoretisches mathematisches Berechenbarkeits-Modell. Mit diesem Modell kann zwar die P/NP Thematik beschrieben werden, Turing Maschinen sind aber weder die "Grundlage" hinter P und NP, noch bei weitem nicht die einzige Möglichkeit, sich der P/NP Thematik anzunähern oder diese mathematisch zu beschreiben.
    Das meinte ich mit Halbwissen.


    Quote

    Eine Turing-Maschine ist ein einfacher Apparat, der in der Lage ist, genau jene Probleme zu lösen, die auch ein Computer zu lösen imstande ist.


    Wenn der Satz stimmen würde, wäre die Frage, ob P=NP ist oder nicht, nur in der Theorie relevant. Gäbe es Computer, welche Instanzen einer nichtdeterministischen Turing-Maschine darstellen, so könnten wir jedes NP-vollständige Problem in polynomieller Zeit lösen.
    Bis Quanten-Computer in die Läden kommen, wird es aber noch etwas dauern...


    Quote

    Formal sind P und NP nun so definiert: Jedes Problem, das in P liegt, kann von einer deterministischen Turing-Maschine in polynomieller Zeit gelöst werden; und jedes Problem, das in NP liegt, kann von einer nichtdeterministischen Turing-Maschine in polynomieller Zeit gelöst werden.


    Formale Definition ist das aber keine und daneben auch ungenau. Um die Definition etwas zu formalisieren:
    Ein Problem X liegt in P, wenn für dessen Lösung ein Algorithmus existiert, der alle Instanzen dieses Problems auf einer deterministischen Turing-Maschine korrekt lösen kann und dessen Laufzeit im Worst-Case für alle Instanzen in der Laufzeit polynomiell beschränkt ist.
    Zumindest drei Ergänzungen, um deine "Definition" wirklich etwas zu formalisieren.


    Quote

    Es lässt sich aber jede nichtdeterministische Turing-Maschine, die eine polynomielle Laufzeit aufweist, in eine deterministische Turing-Maschine umwandeln, deren Laufzeit exponentiell ist.


    Der Satz ergibt so keinen Sinn und ist daneben auch falsch. Du schreibst weder, dass diese Aussage nur hinsichtlich eines bestimmten Problems stimmen kann und auch nur hinsichtlich der Worst-Case Laufzeit.


    Die restlichen Dinge kannst du dir selbst raussuchen, wenn du dich in die Materie mal eingelesen hast.
    Und komm jetzt nicht mit "das habe ich ja alles anders gemeint". Wenn du es anders meinst, dann musst du es in einem Beweis, der sich anmaßt, die P/NP Frage zu lösen, auch hinschreiben.


    Zum Schluss noch ganz allgemein zum Beweis - nur weil du es nicht geschafft hast, für ein (!) NP-vollständiges Problem auf drei Seiten einen polynomiellen Algorithmus zu finden, bedeutet das nicht, dass du die Frage P=NP gelöst hast.


    Ein gut gemeinter Tipp: Versuche bei zukünftigen Beweisen Ungenauigkeiten und Halbwissen zu vermeiden, definier' Dinge auf formale Weise und ziehe daraus formale Schlüsse (mittels Beweisen), vielleicht wird's dann was mit der Lösung von P=NP.



    Zum Suchraum:
    Es geht darum, ob man unbedingt exponentiell viele Lösungskandidaten untersuchen muss, um mit einem (in polynomieller Zeit ablaufenden) Algorithmus die richtige Lösung finden zu können.


    Dass diese Aussage eine Tautologie ist, ist dir aber schon klar?


    Quote from emptyvi

    Aber falls du (oder wer anderer hier) ihn schon gesehen hat.. werden die Begriffe darin "richtig" verwendet, oder ist das wieder so ein Hollywood-OMG_ER_HAT_DAS_INTERNET_GEHACKT-ähnlicher Film?


    Nein, leider noch nicht. Hoffentlich kommt bald ein Screening in unsere Gegend. :)

    Das ist so ein Fall, wo mit einem Algorithmus in P der Suchraum auf eine polynomielle Zahl (z. B. 1) heruntergebrochen werden kann.


    Beim 3-Färbungsproblem kann ich den Suchraum auf jeden Fall auf 2^d (bei n = 4d) herunterbrechen, dieser Wert ist aber exponentiell. Ich kann den Suchraum auch auf eine polynomielle Zahl herunterbrechen, nur bleibt die Frage offen, ob das in polynomieller Zeit möglich ist. Bisher habe ich keinen polynomiellen Algorithmus gefunden.


    Du verwendest den Begriff des Suchraums imho komisch ...
    Falls du mit "Suchraum" die Anzahl der möglichen Lösungskandidaten für ein Problem meinst, so ergeben deine Aussagen im PDF und hier im Thread keinen Sinn. Falls du damit die Anzahl der Lösungen meinst, die dein Algorithmus durchsuchen muss, so sagst du im Wesentlichen: Wenn es einen in der Laufzeit polynomiell beschränkten Algorithmus für ein NP-vollständiges Problem gibt, so gibt es einen in der Laufzeit polynomiell beschränkten Algorithmus für ein NP-vollständiges Problem.


    Sorry, aber auch abgesehen davon strotzt dein PDF nur von Fehlern, generalisierenden oder falschen Annahmen und va Halbwissen (von der Beweisstruktur etc gar nicht zu reden), dass man gar nicht auf alle eingehen kann... (Literaturrecherche ist echt kein schlechter Tipp, möchtest du dich einmal wirklich ernsthaft mit dem P=NP Problem beschäftigen)


    Nur eine Anmerkung zur P=NP?-Problematik:


    Du schreibst in deinem PDF folgendes:

    Quote

    Dagegen ist einzuwenden, dass es ja exponentiell viele Permutationen gibt und man
    im schlimmsten Fall fast alle durchprobieren müsste, bis man auf eine stoßen würde,
    bei denen diese Lösungsmöglichkeiten gültig wären.


    Bei der Frage P=NP geht es jedoch - jetzt bewusst salopp und untechnisch formuliert - genau um die Frage, ob man bei NP-vollständigen Problemen den exponentiell großen Suchraum im Worst Case immer komplett durchsuchen muss oder ob es trotz exponentiell großen Suchraums einen Algorithmus gibt, der auch (und gerade) im Worst Case nicht alle Möglichkeiten enumerieren muss, um das Problem exakt zu lösen.


    Es gibt viele Probleme mit exponentiell vielen möglichen Lösungskandidaten (i.e. Suchraum), für welche trotzdem polynomielle Lösungsalgorithmen existieren. m4rs hat dir schon eines genannt. Selbst das Shortest Path - Problem hat exponentiell großen Suchraum, ist aber mit polynomiellen Algorithmen effizient und schnell lösbar.
    Stell dir nun zB vor, ein genialer Graphentheoretiker findet / entwickelt graphentheoretische Lemmata und Sätze, welche die Grundlage für einen polynomiellen Algorithmus zum 3-Färbungsproblems sein können (analog zu zB Eulerschen Pfaden) - schon musst du nicht mehr zwingend alle Lösungskandidaten durchgehen. (davon abgesehen hätte der geniale Graphentheoretiker hiermit nebenbei indirekt auch P=NP bewiesen)


    So und nun um deine Frage auch zu beantworten:

    Quote

    Angenommen, ihr glaubt, das P-NP-Problem gelöst zu haben. Was macht ihr dann?


    Sollte ich P =/= NP bewiesen haben - meine Million Dollar, ewigwährenden Ru(h)m und Professorenstelle an Uni meiner Wahl einfordern.
    Sollte ich P = NP bewiesen haben - ausnutzen, dass ich der einzige bin, der NP-vollständige Probleme (e.g. Primfaktorenzerlegung ;) ) effizient lösen kann und etwas später oben genannte Dinge einfordern.


    /offtopic


    Weil's zum Thema passt:
    Wer von euch hat zufällig schon den Film Travelling Salesman gesehen?

    es ist noch kein Thema, wenn ich die gestrige ÖH-Wahl Aussage des AG-Kandidaten erwähnen darf bezügliche Zugangsmanagement...


    Soweit ich aus seinen Aussagen und der Homepage rausgelesen haben, soll es ja genau nicht auf Noten im Maturazeugnis oder einzelnen Studien-Anfänger-Tests ankommen...
    Davon abgesehen gehört Informatik sicher nicht zu den besonders überfüllten Studien. (oder musstet ihr mal am Boden sitzen oder habt wegen einer Pflicht-LV, in die ihr nicht reinkamt, ein Semester verloren?)

    Hat jemand die VUs "Theorie der Berechenbarkeit" und "Automatisches Beweisen" bei Alexander Leitsch gemacht?


    Ich hab beide im letzten Sommersemester gemacht.


    Sind die LVAs interessant?


    Ja, Prof. Leitsch ist IMHO ein sehr guter Vortragender und bringt den Stoff sehr interessant.


    Braucht man irgendwelche speziellen mathemtischen Vorkenntnisse? (die Beschreibung klingt zumindest recht advanced)


    Nein, nicht wirklich.


    Wie laufen sie organisatorisch ab? (gibt es praktische Übungen mit Provern bzw. Übungen im Allgemeinen?)


    Es gab letztes Jahr je zwei Übungsblätter, bei Berechenbarkeitstheorie theoretische Aufgaben, bei Automatischem Beweisen gab es auch praktische Aufgaben.
    Bei beiden LVs teilte Prof. Leitsch Unterlagen aus (also man bekam das gesamte Skript zu beiden LVs zur Verfügung gestellt).
    Am Ende gabs eine mündliche Prüfung.

    Hallo, an die, die die Prüfung jetzt im Jänner / Februar gemacht haben:
    Wurde bei euch schon die Note im TISS eingetragen?