Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Aussagen zu P und NP, Reduktion
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Aussagen zu P und NP, Reduktion
sb997
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 30.07.2020
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-15


Hallo, ich bin mir unsicher bei folgenden Aussagen:

1) A ∈ P ∧ B ∈ P ⇒ A\B ∈ P
Meine Antwort: Ich denke die Aussage stimmt nicht.

2) A \(\leq \begin{array}{l}
\text {poly} \\
\text {mo}
\end{array}\) B ⇒ B \(\leq \begin{array}{l}
\text {poly} \\
\text {mo}
\end{array}\) A
Meine Antwort: Die Aussage stimmt nicht.

3.) B ≠ Σ* , B ≠ ∅ ∧ A ∈ P ⇒ A \(\leq \begin{array}{l}
\text {poly} \\
\text {mo}
\end{array}\) B
Meine Antwort: hier weiß ich leider nicht so richtig wie ich das interpretieren soll

Ich habe mir versucht das ganze vorzustellen. Mir sind keine wirklichen Gegenbeispiele eingefallen.

Kann mir einer sagen ob meine Antworten stimmen, bitte? DANKE schon mal im Vorraus!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2437
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-15


Ideen:

1) Nutze die Abgeschlossenheit von P.

2) Wann wäre denn die Folgerung, dass B in Polynomialzeit auf A (many-one)-reduzierbar ist, falsch?

3) Du schreibst, du weist nicht, wie das zu interpretieren sei:
Was ist denn da konkret gegeben? Welche Symbole oder Terme sind unklar?


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sb997
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 30.07.2020
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-09-20


Ja, also ich hätte zu 1. jetzt einfach gesagt, nachdem ich nochmal lange überlegt habe, dass man per Definition eine TM hat die A berechnet und eine die B berechnet und jetzt könnte man einfach die TM die A berechnet simulieren. Wenn False ausgegeben wird, geben wir false zurück. Wenn True ausgegeben wird, dann simulieren wie die TM die berechnet. Wenn dann True ausgegeben wird, gibt man false zurück und wenn false ausgegeben wird, dann gibt man true zurück. Und damit weiß man dann, dass A\B ∈ P.

Zu dem Rest hab ich noch nicht so die Ideen wie ich da vorgehen soll... 🙁



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2437
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-09-20


Zu 1)
Das sollte funktionieren.
Etwas abstrakter geht es, wenn man ausnutzt, dass P bspw. unter Vereinigung, Schnitt und Komplement abgeschlossen ist.


Zu 2)
Idee:
Wähle A aus P und B echt schwerer.
A ist dann auf B reduzierbar, aber nicht umgekehrt.


Zu 3)
Weder ist kein Wort in B noch sind alle Wörter in B.
Welche Komplexitätsklasse besitzt B dann mindestens?


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sb997
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 30.07.2020
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-09-20


zu 2) Stimmt. Verstehe Das macht Sinn! 🙂 Danke!

zu 3) meinst du NP?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2437
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-09-20


2020-09-20 14:24 - sb997 in Beitrag No. 4 schreibt:

zu 3) meinst du NP?

Nein, das sicherlich nicht.
Mein Tipp war allerdings auch schlecht/falsch.

Die Idee ist wohl folgende:
Ein Polynomialzeitproblem kann in Polynomialzeit auf ein beliebiges Problem reduziert werden, indem man es löst und jeweils ein zur Zielsprache gehörendes bzw. nicht gehörendes Wort weiterleitet.
Das funktioniert, solange die Zielsprache mindestens ein Wort enthält und mindestens ein anderes nicht.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sb997
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 30.07.2020
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-09-20


Ja also ich verstehe zwar, was du da schreibst und das macht auch Sinn. Aber ich frag mich immer noch wie mir das jetzt weiterhelfen soll. Weil was enthält B denn dann für Wörter, wenn es nicht alle enthält und auch nicht kein Wort enthält.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2437
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-09-20


Völlig egal.
Du brauchst ja nur ein enthaltenes und eines, das nicht darin liegt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sb997
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 30.07.2020
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-09-20


Okay, also enthält B angenommen einfach ein Wort und A ist ein Element von P. Dann soll A polyzeit reduzierbar sein auf B. Das heißt, das was B enthält, enthält auch A oder irgendwie so?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2437
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-09-20


Nein.

Die Reduktion ist einfach:

Falls Wort in A => gib Wort in B an Automat für B weiter.
Falls Wort nicht in A => gib Wort das nicht in B an Automat für B weiter.

Da A in P liegt, lässt sich das in Polynomialzeit lösen, völlig egal wie B aussieht.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sb997
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 30.07.2020
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-09-20


Also wenn es egal ist, ob in B Wörter sind oder nicht und A in P liegt, dann kann man davon ausgehen, dass A reduziert auf B wahr ist, weil wenn das Wort in A ist, dann ist auch in B und wenn nicht in A dann auch nicht in B



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sb997 hat die Antworten auf ihre/seine Frage gesehen.
sb997 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]