KvA-Fragen

Junior Schreiberling

Date of registration: Oct 11th 2005

Friday, February 20th 2009, 10:55pm

1. Laut Skript ist eine Funktion f raumkonstruierbar, wenn es eine DTM M gibt, die bei Eingabe x den Platzbedarf f(|x|) hat. Reicht es, wenn M diesen Platzbedarf bei einem bestimmten x hat oder muss sie für jedes x genau diesen Platzbedarf haben?

2. Laut Skript ist der Platzbedarf die Anzahl der besuchten Bandzellen. Wie kann

raumkonstruierbar sein? Dafür dürfte die TM ja nur einen Teil der Eingabe besuchen.
edit: Mehrband-TM?

3. Hätte eine TM mit leerem $\delta$ den Platzverbrauch 0?

This post has been edited 1 times, last edit by "BLUESCREEN" (Feb 20th 2009, 11:51pm)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

2

Saturday, February 21st 2009, 10:48am

1. Sie muss für jedes x diesen Platzbedarf haben.
2. Korrekt. Mehrband-TM ist hier Sinn der Sache. Irgendwo im Skript oder Vorlesung wurde ja auch erwähnt, dass bei solchen Komplexitätsmaßen es nur Sinn mit einem separaten Eingabeband macht.
3. Ja, sofern Du mit Platzverbrauch die besuchten Bandzellen meinst.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

BLUESCREEN

Junior Schreiberling

Posts: 244

Date of registration: Oct 11th 2005

3

Sunday, February 22nd 2009, 7:27pm

Quoted from "Arne"

2. Korrekt. Mehrband-TM ist hier Sinn der Sache. Irgendwo im Skript oder Vorlesung wurde ja auch erwähnt, dass bei solchen Komplexitätsmaßen es nur Sinn mit einem separaten Eingabeband macht.

Es steht nur ganz am Anfang des Skriptes, dass sowohl Einband als auch Mehrband genutzt werden. In einer Musterlösung von 2005 (Link geht irgendwie gerade nicht) wird explizit von Einband ausgegangen.

Übungsblatt 3, Aufgabe 3 (b): Liegt Typ 1 in EXP? Die Anzahl der möglichen Konfigurationen ist ja endlich ( $|Z| \cdot (|w| + 2) \cdot |\Gamma|^{|w|}$ ) und jede Maschine sollte laut Skript stoppen.

Sind die Skripte als Hilfsmittel erlaubt? Bei den alten Klausuren steht es immer so drin, aber auch damals stand es nicht auf der Website.

Warum enthält E bei ungerichteten Graphen in der Vorlesung immer Tupel? Eigentlich müssten es doch Mengen sein, da ungerichtet. Oder ist jede Kante doppelt enthalten, also als (u,v) und (v,u)?

Muss man, um zu zeigen, dass ein Problem $A \in PO$ ist, auch zeigen, dass $A \in NPO$ ?

This post has been edited 1 times, last edit by "BLUESCREEN" (Feb 23rd 2009, 2:27am)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

4

Monday, February 23rd 2009, 11:00am

Quoted from "BLUESCREEN"

Quoted from "Arne"

2. Korrekt. Mehrband-TM ist hier Sinn der Sache. Irgendwo im Skript oder Vorlesung wurde ja auch erwähnt, dass bei solchen Komplexitätsmaßen es nur Sinn mit einem separaten Eingabeband macht.

Es steht nur ganz am Anfang des Skriptes, dass sowohl Einband als auch Mehrband genutzt werden. In einer Musterlösung von 2005 wird explizit von Einband ausgegangen.

Das liegt daran, dass hier Funktionen berechnet werden, die auf jeden Fall mehr Platz benötigen als die Eingabe. Also brauch man kein extra Eingabeband.

Quoted from "BLUESCREEN"

Übungsblatt 3, Aufgabe 3 (b): Liegt Typ 1 in EXP? Die Anzahl der möglichen Konfigurationen ist ja endlich ( $|Z| \cdot (|w| + 2) \cdot |\Gamma|^{|w|}$ ) und jede Maschine sollte laut Skript stoppen.

Endlich in Abhängigkeit zu der Eingabelänge |w|! Also linear. Typ1 liegt in LINSPACE. Und damit auf jeden Fall über SPACE(1).

Quoted from "BLUESCREEN"

Sind die Skripte als Hilfsmittel erlaubt? Bei den alten Klausuren steht es immer so drin, aber auch damals stand es nicht auf der Website.

Auf unserer Startseite ist ein Link zur Klausurenübersicht. Es ist (wie das letzte Semester) nur ein DinA4 Zettel belieibig beidseitig beschrieben/bedruckt zugelassen.

Quoted from "BLUESCREEN"

Warum enthält E bei ungerichteten Graphen in der Vorlesung immer Tupel? Eigentlich müssten es doch Mengen sein, da ungerichtet. Oder ist jede Kante doppelt enthalten, also als (u,v) und (v,u)?

Das ist alles geschmackssache. Wenn man Graphen kodiert, verwendet man i.d.R. Tupel für die Kanten. Wenn die Kanten ungerichtet sind, würde natürlich auch reichen nur das Tupel (u,v) in der Menge zu haben. Man weiß ja schließlich, dass man von ungerichteten Kanten ausgeht. Eine andere Möglichkeit ist Katen mit Adjazenzlisten darzustellen. Dann hast du so eine Art Mengenschreibweise, wie von dir angedacht. Kannst du machen wie du willst.

Quoted from "BLUESCREEN"

Muss man, um zu zeigen, dass ein Problem $A \in PO$ ist, auch zeigen, dass $A \in NPO$ ?

Skript S. 32: Ein Problem

gehört zur Klasse PO falls $A\in\text{NPO}$ und falls es einen det. Polynomialzeit-Alg. gibt, der bei Eingabe von $x\in I_A$ eine Lösung $y^*\in Sol_A(x)$ ausgibt. Also: ja.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page