MastersForum

Bääh, theoretische Informatik.
Aber trotzdem coole Sache - ist das jezt anerkannt, wird gerade geprüft oder wie läuft das nun genau ab?

Da freue ich mich schon, wenn unsere eingerosteten Profs ihre alten Skripte aktualisieren müssen.

Wird denn davon ausgegangen, dass die Lösung richtig ist? Ich hab auch mal von diesem Prof gehört, der schon zig Veröffentlichungen gemacht hat, in denen er glaubte, die Riemannsche Vermutung bewiesen zu haben, aber es wurden immer wieder Fehler gefunden.

Man könnte sagen, die Lösung ist anerkannt, wenn innerhalb von zwei Jahren keine behebbaren Fehler/Luecken im Beweis gefunden werden, denn dann sollte die Autoren eine Millionen Dollar fuer die Lösung dieses Millenium-Problems erhalten.

Jetzt macht das Leben von einigen Informatikern wohl noch weniger Sinn

Damn, muss mir jetzt wohl einen neuen Studiengang suchen.

Hmm, naja... mal abwarten. Sieht auf jeden Fall interessant aus, auch wenn ich bisher nur den Abstract gelesen habe. Die verwendeten Konzepte finde ich auf jeden Fall toll. Muss heute abend mal genauer lesen.

Quoted

Original von Tsu_Cortes
Damn, muss mir jetzt wohl einen neuen Studiengang suchen.

Habt ihr nicht erwartet, dass es irgendwann mal in dieser Richtung gezeigt wird?

Ich mein ich kenn mich da nicht so richtig aus, finde seine Beweisidee aber interessant.
Er macht einen beweis durch Widerspruch, indem er bestimmte er sagt es gilt P = NP und daraus bestimmte Eigenschaften für P folgert, welche diese nicht haben kann. Dazu benutzt er irgendwie die Markov-Eigenschaft und sufficient statistics. Eine Statistik, d.h. eine borel-messbare (oder bzgl. der verwendeten sigma-Algebra messbare) Funktion, heißt sufficient für ein Maß mu, genau dann wenn die konditionale Verteilung der Stichprobe, gegeben die Statistik, nicht von mu abhängt. So bekommt er eine Unabhängigkeit hin, d.h. die Verteilungen faktorisieren. Die Verbindung danach zu "first order computations" versteh ich nicht mehr.

Naja, ich glaube zwar das tatsächlich N != NP gilt, aber dass dies nicht der 1 Mio. $ Beweis ist. Bei einem Widerspruchsbeweis wird es sehr drauf ankommen, was für Annahmen er an den Algorithmus stellt, die er zum Widerspruch führen will. A priori ist nicht klar, ob jeder polinomielle Algorithmus diese Annahmen/Eigenschaften auch haben muss. Daran wird es wohl kranken...

Ich denke aber es ist eine sehr interessante Geschichte und die Beweisidee ist neu und daraus lassen sich sicher einige andere Ergebnisse herleiten, wenn vielleicht auch nciht den kompletten Beweis.

wtf hä?

Quoted

Original von Sheep
Noja, es wäre die naheliegendere Variante. Wobei man für "P = NP" nur ein kleines Schlupfloch bräuchte, es würde reichen ein NP-Problem auf ein P-Problem abzubilden. Weil alle anderen NP-Probleme wiederum auf dieses eine NP-Problem abgebildet werden können, sofort könnte man alles in Polynomialzeit lösen...

Da es aber auf diesem Weg relativ "einfach" gehen würde, das aber noch niemand geschafft hat, ist es relativ wahrscheinlich dass P!=NP.
Kann ja nicht alles so einfach sein, wie z.B. PSPACE=NPSPACE.

Quoted

Original von Sheep
Fred.

d.h.?

Quoted

Original von Sheep
Wobei man für "P = NP" nur ein kleines Schlupfloch bräuchte, es würde reichen ein NP-Problem auf ein P-Problem abzubilden. Weil alle anderen NP-Probleme wiederum auf dieses eine NP-Problem abgebildet werden können, sofort könnte man alles in Polynomialzeit lösen...

Ein äußerst schwaches Argument, wie ich finde. Es ist ja schon der ganze Beweis, wenn man für einen Vertreter der NP-Klasse zeigen würde, dass er auch in P liegt. Das ist kein kleines Schlupfloch, sondern wäre ein riesen verfickter Dammbruch: ein direkter Beweis von unglaublicher Schönheit und Mächtigkeit. Ich glaube momentan - mit meinem sehr beschränkten Blick auf dieses Feld - nicht, dass es dazu einen schönen direkten Beweis geben wird. Vielleicht irgendwas abgefucktes theoretisches, was man praktisch nicht nachprogrammieren kann...

Es war ja schon ganz cool zu zeigen, dass man lineare Programme in polynomieller Zeit lösen kann.

@Sheep: ich finde es auch fast etwas arrogant, das Problem der theoretischen Informatik zuzuordnen - dafür ist es mathematisch zu rein, interessant und wichtig.

Glaubt man unter Informatikern echt *eher*, dass NP = P gilt? Für mich sah es immer andersherum aus und mich würde NP = P echt überraschen. Ich mein gibt es irgendwelche Evidenz für NP = P?

http://www.cs.umd.edu/~gasarch/papers/poll.pdf

Quoted

Original von [AA]Hawk
http://www.cs.umd.edu/~gasarch/papers/poll.pdf

Das ist echt mal interessant, thx.

Der Anteil ungleich vs gleich überrascht mich nicht, ebenso wie die Begründung für gleich.

€dit: Der letzte Abschnitt mit den persönlichen meinungen der Mathematiker ist echt interessant. Selbst wenn P = NP, dann muss es keine unmittelbare praktische Bedeutung haben.

Seit ich die News auf Heise gelesen hab, versteh ich auch als nicht Student ungefähr worum es hier eigentlich geht...

http://www.heise.de/newsticker/meldung/P…en-1052857.html

Quoted

Original von Sheep

Quoted

Original von AtroX_Worf

Quoted

Original von Sheep
Fred.

d.h.?

Das galt Fred, der vor dem Posting gepostet hatte.

Achso, solche "Beiträge" ignoriere ich.

Quoted

Original von Sheep
Ansonsten: Ist ja schön, dass es dich interessiert, aber was soll ich zu deinen spontanen Meinungen zum Thema noch groß sagen? Kannst du ja sehen wie du willst...

Jetzt muss ich mal fragen: wtf hä?
Du "sollst" zum Thema gar nichts sagen, nur war rückblickend die Überschriftenwahl etwas einseitig, ich sehe das Thema weniger bei der theoretischen Informatik, als bei der reinen Mathematik. Natürlich ist es absolut wichtig für die theoretische Infromatik, aber nicht nur für sie. Und die Problemformulierung sowie der Abstraktheitsgrad und die Methodik sprechen doch klar für Mathematik... welche man ja durchaus auch als Informatiker benutzen darf... wenn du auf meine Klassifikation anspielst.

Das ja interessant, kannst du mal genauer erklären warum du das Thema mehr bei der reinen Mathematik siehst?

Quoted

Original von Zecher_Falcon__
Das ja interessant, kannst du mal genauer erklären warum du das Thema mehr bei der reinen Mathematik siehst?

Quoted

Wikipedia jeweils:
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties:
...
Computational complexity theory is a branch of the theory of computation in computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty.
...
Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie.

Ich würde die konkrete Frage eher bei der reinen Mathematik einordnen, weil es eine mathematische Frage ist, welche nur mit mathematischen Hilfsmittel entschieden werden kann.

Die Frage ist eine mathematische, weil sie mathematisch formuliert ist und letztlich auch nur mathematisch gelöst werden kann.

Das Problem stellt die Frage nach der Klassifikation von Algorithmen. Vor allem im noch recht neuen Teilbereich der diskreten Mathematik (Graphentheorie etc.) sind diese Fragen enorm wichtig. Dieser Teilbereich hat natürlich eine sehr große Schnittmenge mit theoretischer Informatik, welche die meisten Bereiche der diskreten Mathematik untersucht. Aber wie in der theoretischen Physik oftmals ist es auch in der theoretischen Informatik nicht anders, dass die verbindung zum realen Untersuchungsgegenstand so weit in der Mathematik verloren geht, dass man letztlich nicht mehr all zu gut Unterschieden kann. Dann finde ich sollte man einfach fragen, was für Methoden angewendet werden um Probleme zu lösen und danach katalogisieren. Beim P vs. NP Problem sind es imho rein mathematische Methoden, weil auch automatisierte Beweismaschinen etc. eher theoretische Konstrukte sind und weniger real gebaut werden, um diese Probleme zu lösen.
Man kommt leicht in eine Grenzregion der computergestützten Beweise, aber das P vs. NP Problem lässt sich, meines Erachtens, eher nicht so gut mit computergestützten Beweisen zeigen, zumindest die favorisierte ungleich-Variante nicht.

Quoted

Ich würde die konkrete Frage eher bei der reinen Mathematik einordnen, weil es eine mathematische Frage ist, welche nur mit mathematischen Hilfsmittel entschieden werden kann.

Die Frage ist eine mathematische, weil sie mathematisch formuliert ist und letztlich auch nur mathematisch gelöst werden kann.

Bekommt man an der Uni heute schon Punkte wenn man absolute sinnlose Scheisse im Kreis runterbetet? Wenn ja dann studiere ich jetzt auch einfach mal Mathe....

Quoted

Original von Randy Hicky

Quoted

Ich würde die konkrete Frage eher bei der reinen Mathematik einordnen, weil es eine mathematische Frage ist, welche nur mit mathematischen Hilfsmittel entschieden werden kann.

Die Frage ist eine mathematische, weil sie mathematisch formuliert ist und letztlich auch nur mathematisch gelöst werden kann.

Bekommt man an der Uni heute schon Punkte wenn man absolute sinnlose Scheisse im Kreis runterbetet? Wenn ja dann studiere ich jetzt auch einfach mal Mathe....

Wenn du etwas nicht verstehst, heisst es nicht, dass es sinnlos. Aber schreib dich ruhig mal ein und poste wie gut du voran kommst. Wenn ich raten muesste, was fuer eine Art Mathestudent du wärst, wuerde ich auf 23. Semester und in der Fachschaft tippen.

Quoted

Original von Randy Hicky

Quoted

Ich würde die konkrete Frage eher bei der reinen Mathematik einordnen, weil es eine mathematische Frage ist, welche nur mit mathematischen Hilfsmittel entschieden werden kann.

Die Frage ist eine mathematische, weil sie mathematisch formuliert ist und letztlich auch nur mathematisch gelöst werden kann.

Bekommt man an der Uni heute schon Punkte wenn man absolute sinnlose Scheisse im Kreis runterbetet? Wenn ja dann studiere ich jetzt auch einfach mal Mathe....

Das ist kein Kreis - oder vielleicht exklusiv für dich, wenn du nicht weißt, was mathematisch bedeutet. Die erste Aussage bezieht sich auf die verwendeten Werkzeuge, was ich aber für eine Klassifikation für noch nicht ausreichend erachte, darum verschärfe ich die Aussage mit einem parallel Satzaufbau, dass man nicht nur mathematische Hilfsmittel zur Entschiedung braucht, sondern sie an sich auch nur mathematisch gelöst werden kann. Dies grenzt die Frage von naturwissenschaftlichen Fragen ab, die ich nicht "lösen" kann.
Manchmal versteckt sich eben auch in der Feinheit der Worte die Argumentation.

Quoted

Original von GEC|Napo
Wenn ich raten muesste, was fuer eine Art Mathestudent du wärst, wuerde ich auf 23. Semester und in der Fachschaft tippen.

made my day

fachschaftsleute mag wirklich keiner, oder?

Quoted

Original von GEC|Napo

Quoted

Original von Randy Hicky

Quoted

Ich würde die konkrete Frage eher bei der reinen Mathematik einordnen, weil es eine mathematische Frage ist, welche nur mit mathematischen Hilfsmittel entschieden werden kann.

Die Frage ist eine mathematische, weil sie mathematisch formuliert ist und letztlich auch nur mathematisch gelöst werden kann.

Bekommt man an der Uni heute schon Punkte wenn man absolute sinnlose Scheisse im Kreis runterbetet? Wenn ja dann studiere ich jetzt auch einfach mal Mathe....

Wenn du etwas nicht verstehst, heisst es nicht, dass es sinnlos. Aber schreib dich ruhig mal ein und poste wie gut du voran kommst. Wenn ich raten muesste, was fuer eine Art Mathestudent du wärst, wuerde ich auf 23. Semester und in der Fachschaft tippen.

Ich würde die konkrete Frage eher bei der reinen Pädagogik einordnen, weil es eine pädagogische Frage ist, welche nur mit pädagogischen Hilfsmittel entschieden werden kann.

Die Frage ist eine pädägogische, weil sie pädagoggisch formuliert ist und letztlich auch nur pädagogisch gelöst werden kann. Na Napo dämmerts? Du musst ihm ja nicht ewig dankbar dafür sein das er Dir beim rechnen geholfen hat.

Das Problem ist nur, dass wir alle wissen was pädagogisch und mathematisch heißt. Deswegen macht es Sinn zu sagen, dass es eine mathematische Frage ist, aber es macht keinen Sinn zu sagen es ist eine pädagogische Frage.

Diese Frage kann beispielsweise gar nicht pädagogisch gelöst werden, weil es in der Pädagogik kein Aussagenlogik über abstrakte Aussagen gibt. Man kann mit pädagogischen Hilfsmitteln keine Probleme lösen, welche keine realweltliche Entsprechung haben. Das P vs. NP Problem existiert nur abstrakt derart, dass es zur Formulierung schon Mathematik benötigt.
Dies war die erste meiner Aussagen.

Als zweites kann das Problem nur mit mathematischen Hilfsmitteln entschieden werden. Man beachte, dass ich hier erst beim entscheiden bin, noch nicht beim lösen! Ich glaube dich überfordert die Parallelität meiner Sätze und die feine Unterscheidung in entscheiden und lösen. Anders kann ich mir deine letzten Antworten nicht erklären, obwohl ich schon weiter oben erläutert habe, wie sie zu verstehen sind.

Die Frage nach der Entscheidungsfähigkeit macht die Frage überhaupt interessant. Nicht alle Fragen können entschieden werden und nicht alle entscheidbaren Fragen können mit allen Hilfsmitteln entschieden werden. Beispielsweise kann die Frage ob Gummibärchen süß schmecken nicht durch Mathematik entschieden werden, die Frage ob 1+0=1 ist kann dagegen nur mathematisch entschieden werden.
Dies ist der zweite Teil meiner Ausage.

Der dritte Teil widmet sich dann der letztendlichen Lösung. Ich glaube dies sollte jetzt offensichtlich sein, ich will mich nicht nochmal darüber auslassen, welche Fragen überhaupt lösbar sind etc. Das wäre auch ein bisschen wie "Perlen vor die Säue werfen", um mal Luthers Übersetzung zu zitieren.

Ahso ich bin also die Sau. Nein der Herr beleidigt nie.

Du weißt schon, dass dieser Ausspruch nicht wörtlich zu bewerten ist, sondern einen feststehenden Sinn hat - deswegen auch die Anführungszeichen.