Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » NP-harte entscheidbare Probleme außerhalb NP
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule NP-harte entscheidbare Probleme außerhalb NP
Apfel42343
Neu Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-04


Hallo :)

Ich habe aktuell in zwei Teilaufgaben meiner Hausaufgabe ziemlich Schwierigkeiten.

(1)
Geben Sie ein entscheidbares Problem an, welches NP-Hart aber nicht in NP ist. Begründen Sie kurz Ihre Aussage

(2)
Können Sie ein NP-vollständiges Problem angeben, das in 𝑂(𝑛80) Schritten durch eine DTM berechenbar ist? Begründen Sie kurz Ihre Antwort.

Zu (1): Es soll angeblich Probleme geben, auf die das zutrifft. Jedoch habe ich nach ewigem Gesuche nichts gefunden :/ Auch generell verstehe ich nicht, wie das überhaupt sein kann. Nach meinem Verständnis, waren die NP Hart Probleme Unentscheidbar (bspw. Halteproblem). Zählt man NP-Vollständig nicht zu NP-Hart (wovon ich ausgehe), dann dürfte es doch garkein entscheidbares Problem in NP-Hart geben?

Zu (2): Auch hier soll es (angeblich) ein NP-Vollständiges Problem geben, was darauf zutrifft. Das verstehe leider wieder nicht, da wenn es stimmen würde, die Frage P = NP doch geklärt wäre? Wenn eine DTM ein NP vollständiges Problem in polynomieller Zeit lösen könnte, könnte man doch durch Reduktionen alle Probleme in NP damit lösen?!

Vielleicht sieht ja jemand meine Denkfehler und kann helfen oder stimmt mir zu und die "Gerüchte" sind falsch.

Vielen Dank und Liebe Grüße🙂



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6041
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-04


Hallo Apfel42343 und willkommen auf dem Matheplaneten!

Was meinst du mit n80? \(n80=80\cdot n\) oder \(n80=n^{80}\)? Und vor allem: was ist hier n?

Wenn n die Länge des Inputs ist, hast du recht: Solch ein Problem kannst du nicht finden oder du wärst reich.

Vielleicht schreibst du ja mal die komplette Aufgabenstellung hier hin.

Grüße
StrgAltEntf



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Apfel42343
Neu Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-04


Hallo StrgAltEntf und vielen Dank für deine Antwort :)

Da ist mir Fehler bei der Schreibweise unterlaufen, sorry!
"O(n80)" soll natürlich O(n^80)/("n hoch 80") sein und
n steht für die Länge der Eingabe. Generell denke ich, geht es aber nicht
um die spezielle Laufzeit von O(n^80), sondern um eine generelle
polynomielle Laufzeit.

Die Aufgabenstellung ist schon komplett😂 Also außer, der Fehler mit der Potenz steht auf dem Aufgabenblatt zu der Aufgabe nicht mehr als hier gegeben.

Alles klar, dann Danke für deine Bestätigung zu (2) :) Hättest du noch Idee/Ansätze zu (1) ?


 



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6041
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-04


In der Aufgabenstellung steht nicht, was n ist? Das ist merkwürdig.

Oft ist es so, dass ein Algorithmus für ein bestimmtes \(n\in\IN\) etwas berechnet, n aber in Dezimaldarstellung gegeben ist. Dann wäre die Eingabelänge nur log n, und eine Rechendauer von n^80 wäre dann exponentiell in der Eingabelänge.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Apfel42343
Neu Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-07-04


Es steht nichts explizit in der Aufgabenstellung, aber da wir in der
VL und anderen Aufgaben immer nur "n" als Länge der Eingabe betrachtet haben und keine zusätzlichen Informationen gegeben sind, denke ich, dass es hier nicht anders sein wird.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 1967
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-07-05


Hallo Apfel,

herzlich willkommen auf dem Matheplaneten. 🙃

Zu Frage 1: Deine Annahme, dass alle NP-harten Probleme unentscheidbar seien, ist falsch. In der Tat sind NP-vollständige Probleme insbesondere NP-hart - und zusätzlich noch in NP. Genau das ist doch die Definition von NP-Vollständigkeit. NP-vollständige Probleme sind also sozusagen die "leichtesten" NP-harten Probleme.

Das andere Extrem sind die unentscheidbaren Probleme wie das Halteproblem; dies sind gewissermaßen die "schwersten" NP-harten Probleme (wobei es auch hier noch unermesslich viele unterschiedliche Schwierigkeitsgrade gibt).

Es liegt nahe, dass es auch noch Probleme dazwischen geben sollte. So erscheint es z.B. sehr plausibel, dass es gewisse Probleme gibt, die sich zwar nichtdeterministisch in exponentieller, aber nicht in polynomieller Zeit lösen lassen und gleichzeitig bei der Lösung NP-harter Probleme helfen.

Ein konkretes Beispiel dafür zu finden, erscheint mir indessen gar nicht so einfach. Auf Stack Exchange werden zwei natürliche Beispiele genannt
Ich nehme aber an, dass die Beweise nicht ganz einfach sind, also ob dir das für deine Hausaufgabe etwas nützt ...?

Je nachdem, welche theoretischen Sätze über die Hierarchie der Komplexitätsklassen ihr gelernt habt, kannst du vielleicht auch mit einem davon argumentieren.

Bei Teil (2) würde ich, wenn n wirklich die Länge der Eingabe ist, auch sagen, dass es ein solches Problem nicht geben kann (außer P=NP gilt), wie du ja richtig argumentiert hast.

Viele Grüße

Thorsten




-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   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: 6438
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-07-05


(2) ist geklärt.

Für (1) brauchst Du ein Problem, dass nicht(!) in NP liegt. Schau Dir Deine Vorlesungsmitschrift an. Ihr habt vermutlich irgendwann verschiedene Komplexitätsklassen behandelt und dabei über "echte Inklusionen" gesprochen.
Du brauchst eine Klasse, die NP enthält, aber mit Sicherheit echt größer ist als NP.
Wahrscheinlich wurde auch ein Problem X angegeben, dass in der größeren Klasse liegt, aber nicht in NP.

Du musst dann "nur" noch nachweisen, dass dieses Problem NP-hart ist.
Finde dazu ein NP-vollständiges Problem Y, das in Polynomialzeit auf X reduzierbar ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   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 nor 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]