Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Schnitt von NP-schweren Problemen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Schnitt von NP-schweren Problemen
teacher97
Neu Letzter Besuch: im letzten Monat
Dabei seit: 04.07.2020
Mitteilungen: 1
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-04


Hallo :)
Anbei ist ein Bild einer Aufgabe bei der ich am verzweifeln bin :/ Mir ist zwar schon klar, dass ich den Hinweis nehmen kann, um die Aussage zu zeigen, aber bin halt ratlos wie genau ich das machen muss :/
Vllt kann mir jemand einen Tipp bzw Ansatz verraten wie es zu machen ist :)
Würde mich sehr freuen :)
Vielen Dank schon einmal :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 689
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-04


Hallo teacher97,

das ist nicht schwer,
denn der Schnitt ist leer.

(Spontanreim)

EDIT: ich komme bis zum Folgenden:

\[
\forall z\in\Sigma^\ast: z\notin L_1
\]
wobei \(L_1\) ein beliebiges NP-schweres Problem ist.

Es scheint nicht so einfach zu sein...

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 689
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-07-04


Ich bin der Meinung, dass der Schnitt beider in der Aufgabe gegebenen Sprachen leer ist.

Sei \(L_1\in\mathsf {NP}\). Gesucht ist eine berechenbare Funktion \(f\colon\Sigma^\ast\to\Sigma^\ast\), deren Zeitbedarf polynomiell in der Eingabelänge ist und für die gilt

\[
\forall z\in\Sigma^\ast: z\in L_1\iff f (z)\in 0L\cap1L
\]
das führt auf

\[
\forall z\in\Sigma^\ast: z\notin L_1
\]
was mir ein wenig seltsam vorkommt...

mfg
thureduehrsen



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.3, eingetragen 2020-07-05


Hallo zusammen,

und herzlich willkommen auf dem Matheplaneten, teacher97! 🙂

Genau, der Schnitt der beiden Sprachen ist leer, und damit trivialerweise nicht NP-schwer. Deswegen macht es doch auch keinen Sinn, eine NP-schwere Sprache auf diesen Schnitt reduzieren zu wollen, thureduehrsen?

Was man nur noch begründen muss, ist, warum 0L und 1L auch jeweils NP-schwer sind, wenn L eine NP-schwere Sprache ist. Eine Polynomialzeitreduktion von L auf 0L bzw. 1L ist aber zum Glück ja nicht schwer zu finden.

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.
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 689
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-07-05


Hallo,

ja, ich hätte vielleicht etwas weniger reflexartig vorgehen sollen.

Ich hatte mich nicht nur auf mein Bauchgefühl verlassen wollen (das mich hier dankenswerterweise nicht getäuscht hat), sondern auch formal zeigen wollen, dass die leere Menge nicht NP-schwer ist.

Nehmen wir an, dass \(\varnothing\) \(\mathsf{NP}\)-schwer ist. Dann ist also für jedes Problem \(L_1 \in\mathsf{NP}\) eine in Polynomialzeit berechenbare Funktion \(f\,\colon\Sigma^\ast\to\Sigma^\ast\) anzugeben mit
\[
\forall z\in\Sigma^\ast: (z\in L_1\iff f (z)\in \varnothing)
\]
Sei \(L_1 \in\mathsf{NP}\). Für die gesuchte Funktion \(f\) müsste dann gelten

\[
\begin{array}{rcl}
%&&\textrm{\(0L\cap1L\) ist \(\mathsf{NP}\)-schwer}\\
%&\iff&\\
%&& (\forall z\in\Sigma^\ast: (z\in L_1\iff f (z)\in 0L\cap1L))\\
&&(\forall z\in\Sigma^\ast: (z\in L_1\iff f (z)\in \varnothing))\\
&\iff &(\forall z\in\Sigma^\ast: (z\in L_1\iff \mathbf{falsch}))\\
&\iff &(\forall z\in\Sigma^\ast: z\notin L_1)\\
&\iff& L_1 = \varnothing
\end{array}
\]
und die leere Menge ist in \(\mathsf{NP}\).

Den Widerspruch, den ich erzeugen will, bekomme ich auf diese Weise nicht, wobei aber natürlich nicht jedes Problem in NP gleich der leeren Menge ist.

Ich scheine also irgendetwas zu übersehen.

mfg
thureduehrsen



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 thureduehrsen,

das stimmt schon, auf die leere Menge kann man nichts reduzieren außer die leere Menge selbst.

Aber wie Du ja schon selbst erkannt hast, musst Du die Zeile


2020-07-05 17:42 - thureduehrsen in Beitrag No. 4 schreibt:
Sei <math>L_1 \in\mathsf{NP}</math>.

nur ergänzen zu

"Sei <math>L_1 \in\mathsf{NP}</math> und <math>L_1 \neq \emptyset</math> (z.B. <math>L_1 = 3-SAT</math>)."

Dann funktioniert der Widerspruch, da Du ja am Ende <math>L_1 = \emptyset</math> rausbekommst.

Und natürlich hast Du recht, dass man als Anfänger ruhig beweisen sollte, warum die leere Menge nicht NP-schwer ist und das nicht einfach als "trivial" abtun sollte, wie ich es getan habe. 🙂

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
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 689
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-07-05


Hallo Thorsten,

so wirklich zufrieden bin ich nicht.

Ich muss doch eine Allaussage zeigen, also ansetzen mit "Sei \(L_1\in\mathsf{NP}\)."

Wenn ich von vornherein die leere Menge ausschließe, ist dann mein Beweis noch korrekt?

Und wenn ich den Fall, dass \(L_1=\varnothing\) ist, separat behandle,

\[
\begin{array}{rcl}
&&(\forall z\in\Sigma^\ast: (z\in \varnothing\iff f (z)\in \varnothing))\\
&\iff &(\forall z\in\Sigma^\ast: (\mathbf{falsch}\iff \mathbf{falsch}))\\
&\iff &(\forall z\in\Sigma^\ast: \mathbf{wahr})\\
&\iff& \mathbf{wahr}
\end{array}
\]
was bringt mir das? (Wohlgemerkt ist die leere Menge in NP, aber sie ist nicht NP-schwer.)

Sollen wir das in einem neuen Thread diskutieren?

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: im letzten Monat
Dabei seit: 01.07.2004
Mitteilungen: 857
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-07-05


Hallo,

da ich dazu noch nichts in diesem Faden gelesen habe will ich nur kurz erwähnen, dass die Aussage der Teilaufgabe auch für den Fall NP=P gilt.
(Vielleicht man diese Prämisse im Kontext der Gesamtaufgabe Sinn.)

Gruß Yggdrasil



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.8, eingetragen 2020-07-06


Hallo thureduehrsen,

2020-07-05 22:37 - thureduehrsen in Beitrag No. 6 schreibt:
Ich muss doch eine Allaussage zeigen, also ansetzen mit "Sei <math>L_1\in\mathsf{NP}</math>."

Hm, eigentlich nicht. Du willst doch zeigen, dass die leere Menge nicht <math>\mathbf{NP}\text{-schwer}</math> ist. Es gilt aber:

<math>X \text{ ist } \mathbf{NP}\text{-schwer} \Leftrightarrow (\forall Y \in \mathbf{NP}) Y \leq_p X.</math>

Also negiert:

<math>X \text{ ist nicht } \mathbf{NP}\text{-schwer} \Leftrightarrow (\exists Y \in \mathbf{NP}) Y \not\leq_p X.</math>

 Das heißt, Du benötigst als Gegenbeispiel nur eine Menge <math>Y \in \mathbf{NP}</math>, für die nicht gilt <math>Y \leq_p \emptyset</math>. Und da tut es glücklicherweise fast jede Menge aus <math>\mathbf{NP}</math>, eben außer der leeren Menge selbst.

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
teacher97 wird per Mail über neue Antworten informiert.
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]