[BuK] Bekannte Probleme aus BuK

[philipp]

Ich habe mal eine Liste erstellt, die alle bekannten Probleme zusammenfassen soll. Bitte helft mir sie zu vervollständigen, und die 5 "TODO"s zu beantworten:

http://www-users.rwth-aachen.de/Philipp.Fischer/files/probleme.pdf

philipp

[Fighter_MV]

Sehr gute Liste, so was habe ich gebraucht Mir wa rnämlich in der Präsenzübung ein Problem nicht mehr gängig und so etwas wollte ich nun vermeiden. Danke für die Mühe!!! Hier mal meine Meinungen zu den To Dos.

A_EQ: Nicht rekursiv aufzählbar
Komplement A_EQ: nicht rekursiv, aber rekursiv aufzählbar

POSTAPE: Nicht rekursiv aufzählbar
Komplement POSTAPE: Nicht rekursiv aufzählbar

H_EQ: Nicht rekursiv aufzählbar
Komplement H_EQ: nicht reskursiv und nicht rekursiv aufzählbar


Kleine Ergänzung zu CycleCover:

Jeder Knoten liegt auf genau einem Kreis.

[philipp]

Ok, CycleCover habe ich verbessert, bei den anderen Sachen warte ich nochmal, was die anderen noch so dazu sagen

[heipei]

Bei IndependentSet fehlt ein "n" in der Überschrift.

Ansonsten eine echt schöne Aufstellung, hätte ich damals bei BuK auch gern gehabt

[tobias]

Leider habe ich bis jetzt zu den ToDos auch noch nichts gefunden.

Aber bei der Eigenschaft von POS-Tape steht "LIN-Tape nicht rek.".

[philipp]

Rechtschreibfehler korrigiert

[MartinL]

Bei Postape würd ich sagen ist das Komplement rekursiv aufzählbar. Man kann die entsprechende Turingmaschine auf einer Universellen TM simulieren, die in dem Moment akzeptiert, wo eine Bandpositionen <0 benutzt wird. Die Simulation ist auch möglich, da POSTAPE nach einem konkreten Wort fragt.

Allerdings glaub ich nicht, dass das Komplement von A_EQ rekursiv aufzählbar ist.
Idee für Reduktion von D auf not A_EQ

Man übergibt not A_EQ die Maschine M_i und eine Maschine M*, die prüft ob w auf dem Band steht, wenn ja, dann akzeptiert sie, ansonsten führt sie M_i auf der Eingabe aus.
Wenn nun M_i w nicht akzeptiert, dann ist die Sprache von M_i und M* nicht gleich, also kommt 1 bei raus. Was korrekt ist für D.
Wenn M_i w akzeptiert, dann erkennen M_i und M die selbe Sprache, also kommt 0 heraus, was auch korrekt ist für D.

Also kann man eine nicht rekursiv aufzählbare Sprache auf not A_EQ reduzieren => not A_EQ ist auch nicht rekursiv Aufzählbar.

Oder überseh ich nu irgendwas? ... ich glaub nicht.

Mit dem Rest bin ich soweit einverstanden.

Ergänzung: Vorsicht mit Coloring. Hier sind wenn dann nur Varianten mit 3 und mehr Farben NP - vollständig, auch wenn ich mir nicht ganz sicher bin. 2 - Färben kann man mit Breitensuche lösen.

[mirko]

Ergänzung: Vorsicht mit Coloring. Hier sind wenn dann nur Varianten mit 3 und mehr Farben NP - vollständig, auch wenn ich mir nicht ganz sicher bin. 2 - Färben kann man mit Breitensuche lösen.

die anzahl der farben ist doch teil der eingabe. da man nicht verhindern kann, das jemand 3 eingibt, ist das problem npc

[philipp]

Das mit POSTAPE denke ich auch so. Hab ich jetzt auch mal eingetragen.

Ergänzung: Vorsicht mit Coloring. Hier sind wenn dann nur Varianten mit 3 und mehr Farben NP - vollständig, auch wenn ich mir nicht ganz sicher bin. 2 - Färben kann man mit Breitensuche lösen.

Wenn du so willst, ist auch coloring mit N Farben nicht NP-hart, wenn es N Knoten gibt, weil das dann immer geht... Aber die Anzahl der Farben gehoert ja nicht zur spezifikation des problems sondern ist teil der eingabe. Daher ist es im allgemeinen schon NP-Hart.

Und die Sache mit A_EQ. Ja denke ich auch so. Habe mich gerade trotz deiner einleuchtenden Reduktion an einem Gegenbeweis versucht und da ist es mir klar geworden. Habe ich also auch geaendert.

[Fighter_MV]

ich frage mich auch grade wie darauf kommen konnte, dass es rekursiv aufzählbar ist. Entweder ich hab mich verschrieben oder ich war einfach doof

[MartinL]

H_EQ, sollte sich wie A_EQ verhalten, da man A_EQ auf H_EQ reduzieren kann, indem man die Maschine, immer wenn sie verwirft in eine Endlosschleife schicken kann.

[Commo]

nicht rekursiv aufzählbar mit der Begründung, dass das Teilproblem zwar rekursiv aufzählbar wäre, aber bei alle Eingaben überprüft werden müssen. An dieser Stelle "wirds wieder unendlich" und die rekursive Aufzählbarkeit ist futsch.

Ebenso würde ich bei L(S) argumentieren, nämlich, dass in S Funktionen sein können, die unendlich viele Eingaben akzeptieren. Hier müssten für rekursive Aufzählbarkeit unendlich viele TM auf unendlich viele Eingaben getestet werden. Das hört sich doch sehr unaufzählbar an...

Bei wird in der Musterlösung unterschieden: Falls M w akzeptiert, gilt , ansonsten . ist nicht rekursiv und rekursiv aufzählbar, daraus folgt ist nicht rekursiv aufzählbar. Das Problem ist also entweder im allgemeinen nicht rekursiv aufzählbar oder aber hängt von M ab.

[CrazyPumuckl]

Hi, suche noch je ein Beispiel für folgende Probleme:

1.) Problem aus NP, dass nicht in NPC liegt (und es sollte trivialerweise kein Problem aus P sein)

2.) Problem, dass NP-hart ist, aber nicht in NPC liegt (da es nicht in NP liegt)

[fw]

1.) Problem aus NP, dass nicht in NPC liegt (und es sollte trivialerweise kein Problem aus P sein)

Irgendwie scheint das immer wieder missverstanden zu werden (obwohl das hier schon öfters diskutiert wurde): Es ist NICHT bekannt ob es Probleme gibt, die in NP aber nicht in P liegen! (Diese Frage ist doch genau die Problemstellung des P/NP-Problems)

2.) Problem, dass NP-hart ist, aber nicht in NPC liegt (da es nicht in NP liegt)

Halteproblem

[philipp]

So,
habe das mit dem NumZettel gerade auch schon gemacht. Also hier der Source zu dem BukProbleme-Zettel:

http://www-users.rwth-aachen.de/Philipp ... obleme.tex

Dann könnt ihr den erweitern, wie ihr Lust habt.