Zitat von Adok

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.

Zitat von Adok

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.

Zitat von Adok

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.

Zitat von Adok

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)?

Zitat von Adok

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):

Zitat

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.

Zitat

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...

Zitat

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.

Zitat

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.

Zitat von Adok

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?

Zitat von 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.

Zitat von Adok

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:

Zitat

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:

Zitat

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?

Dass man am Ende nur Bachelor oder Master auswählen darf, ist ziemlich einschränkend, wenn man in einem Doktorat bzw. Diplomstudium studiert...

Zitat von postwarbreakout

Muss ich eigentlich in dem wahllokal wählen, was in der personalisierten mail stand, oder is das egal?

Du musst in dem Wahllokal wählen, das für deine Studienrichtung zuständig ist.

Wer sich als Univ.-Prof. bewirbt, muss doch auch seine gesamte Bibliographie vorlegen (oder nicht?) und das kann dann die CD schon füllen.

Zitat von Juggl3r

Man bedenke:
Durch die Familienbeihilfe verlieren wir Studenten genau 3 (3 Jahre) * 7 ( jeden 2ten Monaten auszwahlung + 13ten Kinderbeihilfe) * 400 € = 8400 €!....

Wir verlieren sogar noch mehr:
Wir müssen uns dann selbst versichern, das Semesterticket wird teurer etc

Zitat von Apfelsaft

Morgen gibt es übrigens eine Demo gegen die Kürzung: http://www.oeh.ac.at/blog/oeh_blog_…Hash=bbd1759bb7

Und dort sollten wir heute alle hingehen, denn das ist neben vielen anderen in der letzten Zeit, wohl die größte Frechheit der Regierung!
(und zur Demo am besten gleich unsere Eltern mitnehmen, denen die "Reformen" wahrscheinlich auch nicht schmecken werden)

Zitat von Venefica

wenn ma davon ausgehen, dass die uni eine foschungseinrichtung ist ..

... und Lehre unter Forschung subsummierbar ist, was ich stark bezweifel.

Wie kann ich aus meinem Code eine .exe erzeugen? (ich verwende Eclipse)
Beim Aufruf mit Run läuft es wunderbar durch, würd die App aber auch gern starten, ohne vorher Eclipse zu laden.
Ist wahscheinlich eh ganz einfach, ich finds aber nicht. :shinner:

WinRAR?

Zitat von AuA!

..., wurden sie auch dort mit den üblichen Störaktionen konfrontiert und mussten unter massivem Polizeischutz aus der Uni abgeführt werden.

Meinst du damit die Gewalt, die angewendet wurde, um die Burschenschafter vom Siegfriedskopf fernzuhalten und die den Einsatz der VEGA erforderte, nur um die streitenden Parteien voneinander zu trennen?
(bin einmal im letzten Semester zufällig dort vorbeigegangen und muss sagen, die VEGA Beamten habens schwer ...)

Fürs Protokoll: Ich kann die Burschenschafter überhaupt nicht leiden.
Aber dass Gewalt nur weitere Gewalt hervorruft, schreckt auch die "Demonstranten" nicht davon ab, sie einzusetzen.

Und wenn Leute, die an einer Uni studieren, Gewalt einsetzen müssen, um ihre Anliegen durchzusetzen, bzw. diese Gewalt erwidern, läuft was schief.

Zitat von fabs

Im Grunde streiten wir uns hier aber nur um eine sprachliche Formulierung.

Stimmt.

Was ich eigentlich kritisiert habe, ist die Aussage, vollkommen und gegenüber jedem tolerant zu sein, dann aber in einem der nächsten Sätze zu sagen, aber dieses und jenes akzeptiere ich nicht.

Aber is auch egal, so wichtig ists mir nicht

Zitat von fabs

Genau das machen wir aber. Es gibt als höchste Güter Meinungs- und Pressefreiheit ("Wir akzeptieren alles."). Und dann gibts (zum Glück, ich würds sogar noch erweitern auf "Verfassungsfeindliche Ideologien") das Verbotsgesetz ("Aber das, das und das nicht.").

Die Meinungsfreiheit wird nur innerhalb der gesetzlichen Schranken gewährt, dh nirgends wird gesagt "Wir akzeptieren alles".

Zitat von Art 10 StGG

Jedermann hat das Recht, durch Wort, Schrift, Druck oder durch bildliche Darstellung seine Meinung innerhalb der gesetzlichen Schranken frei zu äußern.
...

Zitat von Art 13 EMRK

...
(2) Da die Ausübung dieser Freiheiten Pflichten und Verantwortung mit sich bringt, kann sie bestimmten, vom Gesetz vorgesehenen Formvorschriften, Bedingungen, Einschränkungen oder Strafdrohungen unterworfen werden, wie sie in einer demokratischen Gesellschaft im Interesse der nationalen Sicherheit, der territorialen Unversehrtheit oder der öffentlichen Sicherheit, der Aufrechterhaltung der Ordnung und der Verbrechensverhütung, des Schutzes der Gesundheit und der Moral, des Schutzes des guten Rufes oder der Rechte anderer unentbehrlich sind, um die Verbreitung von vertraulichen Nachrichten zu verhindern oder das Ansehen und die Unparteilichkeit der Rechtsprechung zu gewährleisten.

Zitat von fabs

Nicht wirklich. Ab irgendeinem Punkt muss man sich schützen. Sonst könnte man den Verfassungsschutz einstampfen und das Verbotsgesetz aufheben.

Zwischen Ausländerfeindlichkeit bzw. einer kritischen Haltung gegenüber Immigration und nationalsozialistischer Wiederbetätigung wirst aber auch du unterscheiden, oder ist das dasselbe für dich?
Dass die Meinungsfreiheit (als Verfassungsgesetzliches Grundrecht) durch das ebenfalls als Verfassungsgesetz ergangene Verbotsgesetz eingeschränkt wird, ist mir schon bewusst.
Aber dann kann man sich nicht hinstellen und sagen:
Ich akzeptiere alles. Aber das, das und das nicht.

Zitat von fabs

@Religion: Ich würde nur meinen, dass die einzigen zwei Stellen, wo Religion in Gesetzestexten stehen sollte, erstens die Präambel zur Verfassung (unter zu überwindende Dinge wie Armut, Seuchen etc.)

Zum Glück hat sich Österreich dazu entschieden, in die Verfassung nicht so Dinge wie Gott oder ähnliche pathetische Aussagen aufzunehmen, sondern nur nüchtern und klar folgendes zu formulieren:

Zitat

Österreich ist eine demokratische Republik. Ihr Recht geht vom Volk aus.

Zitat von Ivy

Ich weiß, dass ich andere Meinungen zu akzeptieren habe. Aber ich brauche sicher keine ausländerfeindliche Einstellung akzeptieren. Sicher kann ich nix dagegen machen, aber es war schon immer so, dass das einfache Volk immer noch am einfachste zu beeindrucken ist von einem HC oder einem Jörgi. Deshalb nenne ich es Pöbel. Ja. Gemeines, ungebildetes, dummes, manipulierbares Fußvolk.

Dass du dir selbst widersprichst, ist dir aber schon bewusst?
Klingt für mich stark nach "Ich akzeptiere alle anderen Meinungen. Natürlich nur, wenn sie sich mit meiner decken."
Ist aber deine Meinung und ich respektier sie.
Dass du Menschen mit anderer politischer Auffassung beleidigst, spricht auch Bände ...

Ich find den Thread ganz amüsant, über politische Ansichten kann man sich ja ewig streiten...

Zitat von Apfelsaft

Habt ihr schon mal jemanden getroffen den ihr zu kennen dachtet und der auch dachte euch zu kennen, aber ihr beide nicht wusstet ob ihr euch wirklich kennt?

Jep, ist mir passiert, allerdings kannten wir uns wirklich vorher nicht (haben wir jettz im Nachhinein ausgeforscht), obwohl wir beide schwören konnten, uns vorher schon mal getroffen zu haben... strange...

Hi,

ich bin grade dabei, mich mit den Funktionalitäten von Excel vertraut zu machen, allerdings würd es mit einem guten Buch sicher leichter sein

Kennt wer von euch ein gutes Buch zu Excel?

lag doch nicht an der Batterie (so nach 3 wochen hats wieder angefangen zu spinnen, dann habens die batterie wieder gewechselt und nach 3 wochen gings wieder nicht).

Lag daran, dass ein Kontakt am Motherboard falsch verlötet war ...

Danke an alle nochmal
:cool: