Zitat von Paulchen

Dir müsste klar sein, dass es für einen mathematischen Beweis nicht ausreicht, ein einzelnes Beispiel zu bringen. Genau das machst du aber. Du bringst ein Beispiel für einen Algorithmus, der dein NP-vollständiges Problem in nicht-polynomieller Laufzeit löst, und behauptest, es kann daher keinen Algorithmus mit polynomieller Laufzeit für dieses Problem geben.

Ich gehe davon aus, dass es keinen Algorithmus geben kann, der das Problem in polynomieller Laufzeit löst, weil der Suchraum (Anzahl der zu untersuchenden Lösungsmöglichkeiten) exponentiell mit der Größe der Eingabedaten (Anzahl der Knoten des Graphen) wächst. Ich beweise, dass der Suchraum tatsächlich exponentiell wächst - dieser Beweis dürfte hieb- und stichfest sein. Was ich nicht beweise, ist, dass es keinen polynomiellen Algorithmus geben kann, wenn der Suchraum exponentiell wächst. Das nehme ich nur an. Wie gesagt, könnte es sein, dass jemand anderer diesen Zusammenhang bewiesen hat. Es könnte auch sein, dass jemand anderer bewiesen hat, dass dieser Zusammenhang nicht besteht - in diesem Fall wäre die Schlussfolgerung P != NP unzulässig. Sollte aber der Zusammenhang beweisbar sein, wäre P != NP die gültige Schlussfolgerung.

Zitat von Paulchen

Darf ich also zusammenfassen: Du schreibst in der Einleitung deines Textes, dass aus P != NP folgt, dass für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit existieren. Um zu zeigen, dass P != NP gilt, nimmst du an, dass es für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit gibt. Damit hast du zwei Dinge gezeigt:

• Für NP-vollständige Probleme gibt es genau dann keine Lösungsalgorithmen mit polynomieller Laufzeit, wenn es für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit gibt.
• P != NP genau dann, wenn P != NP.

Ich kenne jemanden, der noch Leute sucht, um einen Tautologieclub gründen zu können. Soll ich euch bekannt machen?

Diese Argumentation kann ich nicht nachvollziehen. Es gilt P != NP genau dann, wenn, wie du schreibst, "für NP-vollständige Probleme keine Lösungsalgorithmen mit polynomieller Laufzeit existieren". Wenn ich die rechte Seite dieser Gleichung beweisen kann (wobei es in diesem Fall genügt, für ein einziges Problem in NP zu beweisen, dass kein Algorithmus mit polynomieller Laufzeit existieren kann), dann folgt daraus die linke Seite. Das ist keine Tautologie. Derzeit ist weder die linke Seite noch die rechte Seite bewiesen. Es ist aber auch weder die linke Seite noch die rechte Seite widerlegt. Wenn es gelingt, eine der beiden Seiten zu beweisen, dann folgt daraus, dass auch die andere Seite bewiesen ist. Wenn es gelingt, eine der beiden Seiten zu widerlegen, dann folgt daraus, dass auch die andere Seite widerlegt ist. Genau darum geht es im P-NP-Problem.

Zitat von rosquilla

Aus deiner Argumentation geht mE nicht hervor, warum es tatsächlich notwendig ist exponentiell (sorry "alle" war natürlich nicht richtig) viele Möglichkeiten zu überprüfen. Nochmal: Wodurch schliesst du aus, dass ein Algorithmus existiert, der in polynomieller Zeit läuft?

Wie ich erklärt habe, ist es ab n = 4 Knoten nicht mehr möglich, eine bestimmte Lösung zu nehmen, die für alle möglichen Graphen mit n = 4 Knoten gültig ist, sondern man muss mindestens 2 verschiedene Lösungsmöglichkeiten überprüfen (denn ich habe gezeigt, dass es mindestens zwei Graphen gibt, deren Lösungsmengen zueinander disjunkt sind). Weiters habe ich gezeigt, dass die Anzahl der Lösungsmöglichkeiten, die überprüft werden müssen, mit linear steigender Knotenzahl exponentiell wächst: Bei n = 4d gibt es 2^d Graphen mit 2^d zueinander disjunkten Lösungsmöglichkeiten. Somit ist die Anzahl der Lösungsmöglichkeiten, die mindestens überprüft werden müssen, um garantiert eine gültige Lösung zu finden, nicht polynomiell, sondern exponentiell von der Anzahl der Knoten (also der Größe der Eingabedaten) abhängig. Das habe ich meines Erachtens hieb- und stichfest bewiesen.

Die einzige Schwachstelle, die ich momentan sehe, ist eben die, dass ich davon ausgehe, dass der bestmögliche Algorithmus, bei dem mit der Methode "durchsuche alle in Betracht kommenden Lösungsmöglichkeiten und überprüfe, ob sie gültig sind, bis die erste gültige Lösung gefunden wurde" vorgegangen wird, nicht schlechter sein kann als irgendein anders aufgebauter Lösungsalgorithmus. Das heißt, ich gehe davon aus, wenn es keinen Algorithmus mit dieser Methode gibt, der eine polynomielle Laufzeit hat, dann kann es keinen andersgearteten Algorithmus für dasselbe Problem geben, der eine polynomielle Laufzeit hat. Diese Annahme habe ich nicht bewiesen. Eventuell wurde sie bereits von jemand anderem bewiesen - wenn das der Fall ist, dann dürfte mein Beweis tatsächlich funktionieren. Sollte aber bewiesen werden können, dass diese Annahme falsch ist, würde meine Argumentation in sich zusammenbrechen.

Zitat von rosquilla

Du behauptest, dass du auf jeden Fall alle Möglichkeiten (exponentiell viele) überprüfen musst. Woher weisst du, dass es keinen Algorithmus gibt, der dir erlaubt nur polynomiell viele zu überprüfen?

Ich versuche zu zeigen, dass die untere Schranke der Anzahl der Möglichkeiten, die ich überprüfen muss, exponentiell ist. Man muss nicht alle Möglichkeiten überprüfen, aber in jedem Fall exponentiell viele.

OK. Schaut euch einmal das hier an.

http://www.hugi.scene.org/adok/articles/pnpproblem.pdf

Vielleicht wirkt es wie eine blöde Frage. Die Frage ist aber durchaus ernst gemeint:

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

Hat jemand von euch an diesem Wettbewerb teilgenommen?
http://www.vcla.at/tmaward/

Mir haben die Organisatoren mitgeteilt, dass 7 Projekte von Studierenden eingereicht wurden und keines den Anforderungen entsprochen habe! Deswegen werde nur in der Kategorie "Schüler unter 21 Jahren" ein Preis verliehen.

Ich kann es kaum glauben, dass wir Studenten im Vergleich zu Schülern so schlecht sein können.

Zitat von natty_dread

Adok:

Ich compiliere mittels
gcc -c -Wall -O -o Funktion.o Funktion.c => das funktioniert toll.
gcc -c -Wall -O -o Program.o Program.c => das gibt mir die oben angegeben Fehlermeldungen.

Mit gcc habe ich nicht so viele Erfahrungen, jedoch fällt mir auf, dass in der zweiten Zeile Funktion.o nicht vorkommt. Da Program.c auf die dort definierte Funktion zugreifen muss, muss Funktion.o irgendwie verlinkt werden.

Zitat von natty_dread

Wenn ich das Semikolon einfach im Header entferne, dann spuckt der Compiler trotzdem die selben error Meldungen aus...

Das Semikolon hat auch nicht mit diesen Fehlermeldungen zu tun.

Zitat von natty_dread

Meine Funktionen sind:

#include<stdio.h>
#include<math.h>

double VKugel(double a)
{
return (4./3)*M_PI*a*a*a;
}

double VWuerfel(double A)
{
return A*A*A;
}

Alles anzeigen

In welcher Datei hast du sie definiert, und wie bindest du diese Datei in das Programm ein?

Was jedenfalls falsch ist:

#define rho 7.86;

Da musst du das Semikolon am Ende entfernen. Im konkreten Programm verursacht das zwar keine Probleme, weil du rho immer unmittelbar vor dem Ende der Anweisung benutzt, aber im allgemeinen Fall ist diese Definition falsch.

Mir ist nicht ganz klar: Die Deklarationen sind in Header.h enthalten, gut; aber in welcher Datei definierst du die Funktionen? Vielleicht könntest du auch die Funktionsdefinitionen posten, eventuell ist da etwas fehlerhaft (obwohl es unwahrscheinlich ist, weil das Programm ja funktioniert, wenn du die Definitionen in die Hauptdatei verschiebst).

Zitat von luna12

maxputz: Es dauert einige Zeit bis der benutzer bzw. die benutzerin sich auf die neue Betriebssystemoberfläche sich gewöhnt hat... Oder vermisst du d. Benutzeroberfläche von den früheren versionen des Betriebssystems?

Ich habe lange Zeit MS-DOS benutzt. Windows war vor 1995 nur eine Erweiterung von MS-DOS, die man jederzeit starten konnte. Das Starten von Windows hat allerdings lange gedauert. Da ich nur wenige Windows-Applikationen verwendete, blieb ich meistens im MS-DOS-Modus. Für MS-DOS gab es Dateimanager wie den Norton Commander, mit denen man recht komfortabel arbeiten konnte. Auch jetzt verwende ich noch den Total Commander.

Wenn ich mich recht erinnere, habe ich Windows lange Zeit nur für Word gebraucht. Dann gab es noch ein Programm namens Graphics Workshop, das ich ab und zu verwendet habe. Ansonsten habe ich es nicht benötigt.

Eine andere Möglichkeit wäre, den Code von Paulchen zu verwenden und blubb.length durch blubb.length / 2 zu ersetzen...

Das macht man normalerweise mit einer for-Schleife.

Die Informatik-Fakultät der TU Wien soll sogar zu den 10 besten in Europa gehören. Von einer Ghetto-Uni sind wir also weit entfernt.

Zitat von dv_

Grade gesehen, es gibt ja auch ein Teil 2 und Teil 3 !
Aufgepasst, "in der Computertechnik benutzt man Primzahlen bis 1024" :rofl:
http://www.youtube.com/watch?v=T_F_23Ek3Fg

Interessant, 1024 ist also eine Primzahl? Das ist eine ganz neue Erkenntnis! Ich dachte, die einzige gerade Zahl, die eine Primzahl ist, wäre die 2.

Zitat von Vendredi

Das hab ich mir auch gedacht, bis mir eingefallen ist, dass ich wohl einen fundamentalen Fehler mache.
"Normalo-Logik" hat hier nichts zu suchen, man muss schon diese spezielle, der "alten Logik" völlig überlegenen neue Logik anwenden.

Vielleicht solltest du die Vorlesung über "Nichtklassische Logiken" von Chris Fermüller besuchen

Allein die Aussage "Medizin ist Mathematik, Biologie ist Physik!" ist schon, um es milde auszudrücken, dämlich. Zu Beginn des Medizinstudiums lernt man Chemie, Physik und Biologie. Somit kann Medizin nicht reine Mathematik sein, sondern ist zumindest auch Physik.

Der gesuchte Algorithmus heißt Selection Sort.

Normalerweise geht man zu einem Verein wie Mensa, um Leute kennenzulernen. Es gibt aber auch solche, die einfach zur Mensa gehen, weil sie den Aufnahmetest als Herausforderung betrachten und wissen wollen, ob sie ihn bestehen werden. Das ist genauso, wie wenn man an einem Wettbewerb teilnimmt. Deshalb verlassen viele den Verein auch bereits nach dem ersten Jahr (in dem die Mitgliedschaft kostenlos ist) bzw. verlängern ihre Mitgliedschaft nicht.

Zitat von emptyvi

Hi!

Danke für die Infos! Wenn das gegebene Zitat auf viele Mensa-Mitglieder zutrifft.. Ists dort dann nicht eher zach?

l.g.

Kannst ja mal vorbeikommen und dir selbst ein Bild machen!