Die Mathe-Redaktion - 05.04.2020 07:54 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps für den MP

Werbung

Bücher zu Naturwissenschaft und Technik bei amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 415 Gäste und 7 Mitglieder online

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » NP-Vollständigkeit beweisen lernen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule NP-Vollständigkeit beweisen lernen
rapiz
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2019
Mitteilungen: 74
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-02-23


Moin, komme mit NP Vollständigkeits und polynomiellen Reduktionen nicht zurecht. Kann mir dies jemand erklären und Tipps geben?

Versuche das irgendwie hinzubekommen, es scheitert jedes Mal sobald ich eine Fragestellung dazu habe.



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6285
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-02-24


Es macht ja nicht viel Sinn, den Text aus einem Lehrbuch hier hereinzukopieren. Kannst Du also etwas konkreter werden?

Wesentlich sind m.E. zwei Konzepte:

a) Polynomielle Reduktion
Ich möchte wissen, ob ein Problem A "leicht" zu lösen ist.
So richtig beantworten kann ich die Frage nicht (ob NP=P ist, weiß immer noch niemand). Aber ich bekommen (vielleicht) folgende Antworten:
i) Wenn Problem A leicht ist, dann ist auch Problem B leicht.
Hat man nämlich irgendeine Instanz des Problemes B, dann lässt sich diese Instanz in Polynomialzeit in eine Instanz des Problemes A übersetzen.
Dann könnte man diese übersetzte Instanz lösen (weil A ja "leicht" ist) und hätte damit auch die Lösung für das ursprüngliche Problem.
Diesen Schritt nennt man Polynomialzeitreduktion.
Diese Reduktion ist besonders dann mächtig, wenn ich schon etwas mehr über Problem B weiß, z.B. etwa:
ii) Wenn B leicht ist, dann sind alle(!) Probleme aus NP leicht.
Mit anderen Worten: Problem B ist NP-schwer (mindestens so schwer wie alle Probleme aus NP).
i)+ii) zusammen ergeben die NP-Schwere von Problem A.

Achtung: Polynomielle Reduktion ist als Konzept erstmal unabhängig von der Klasse NP!

b) Nichtdeterministische Berechenbarkeit (in Polynomialzeit)
Dich eine nichtdeterministische Turingmaschine vorzustellen ist nicht ganz leicht. Stell Dir vor, Du hättest ein Programm, bei dem in jeder Zeile nicht eine Anweisung steht, sondern zwei und Du darfst jeder Zeit bestimmen, welche der beiden Anweisungen das Programm ausführen soll.
Ein Programm wird dabei als korrekt angesehen, wenn folgendes erfüllt ist: Ist die Antwort auf die Frage "Nein", dann führen alle Auswahlen der zu verwendenten Anweisungen zum Ergebnis "Nein". Ist die Antwort dagegen "Ja", so reicht eine einzige Folge von Anweisungen, die das Ergebnis "Ja" liefert. [Man beachte, dass man die Rollen von "ja" und "nein" nicht einfach vertauschen kann.]
Man kann es sich auch so vorstellen, dass das Programm eine Lösung "errät" und dann nur überprüfen muss, ob das wirklich eine Lösung ist. Eine nichtdeterministische Turingmaschine kann also exponentiell viele Lösungen _gleichzeitig_ überprüfen.
Diese Sichtweise ist wahrscheinlich leichter zu verstehen, als die mit den zwei verschiedenen Ansätzen, sie ist aber leider nicht ganz so allgemein.
Es könnte sein, dass wir Fragen beantworten, ohne eine "Lösung" zu überprüfen. Aber man erkennt hier vielleicht die "Macht" des Nichtdeterminismus. Die Frage: "Gibt es eine Belegung von n Binär-Variablen, so dass ein bestimmter Ausdruck A wahr wird?" lösst man sehr leicht. Man probiert alle möglichen Belegungen gleichzeitig aus, berechnet die Wahrheitswerte und wenn irgendeiner davon "wahr" ist, so lautet die Antwort "Ja" und umgekehrt.

Ein Problem, dass sich nichtdeterministisch in Polynomialzeit lösen lässt, gehört zur Klasse NP. Ist es außerdem noch NP-schwer, dann nennt man beide Eigenschafte zusammen "NP-Vollständigkeit".



  Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP, that seems no longer to be maintained or supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]