komplexitätsklassen richtig verstanden?

elise

nur zu sicherheit..erstmal allgemein:

DTIME(T) bzw. NTIME(T) ist die klasse aller sprachen L, für die es eine funktion
t element aus T gibt, und eine t-zeitbeschränkte deterministische, bzw. nichtdeterministische maschine M exitistiert, die L akzeptiert.

eine maschine M ist t-zeitbeschränkt, meint, dass jeder akzeptierte algorithmus für eine eingabe der laenge n aus aus höchstens t(n) schritten besteht.

nun speziell P - NP

die klasse P wäre dann DTIME (POL) (menge aller in polynomialzeit lösbarer funktionen, also für die es eine solche funktion f element pol gibt, und eine f-zeitbeschränkte deterministische maschine M existiert, die L akzeptiert)

die klasse NP wäre dann NTIME (POL) (menge aller in polynomialzeit lösbarer funktionen...), wobei hier zuerst "geraten" wird, und das "geratene" in polynomialzeit (durch eine kontrollturinmaschine) verifiziert wird.

somit ist DTIME(POL) eine teilmenge von NTIME(POL)

nur zur sicherheit, vielleicht wollt ich es auch einfach nur aufschreiben.

ich sehe die t-zeitbeschränkten funktionen im grunde als die gemeinhin als O(f) begriffenen funktion an, also O(n), oder ähnliches, lineare laufzeit, konstante laufzeit, exponentielle laufzeit, etc.

den begriff "klasse" verwende ich also in obiger Form einfach als idee von maschinen, die in der jeweiligen "zeit" lösbar sind.

wie auch immer, falls ich ganz falsch liege, tröstet mich.

Hi

die klasse P wäre dann DTIME (POL) (menge aller in polynomialzeit lösbarer funktionen, also für die es eine solche funktion f element pol gibt, und eine f-zeitbeschränkte deterministische maschine M existiert, die L akzeptiert)

die klasse NP wäre dann NTIME (POL) (menge aller in polynomialzeit lösbarer funktionen...), wobei hier zuerst "geraten" wird, und das "geratene" in polynomialzeit (durch eine kontrollturinmaschine) verifiziert wird.

somit ist DTIME(POL) eine teilmenge von NTIME(POL)

Aussagen wie "menge aller in polynomialzeit lösbarer funktionen" gefallen mir nicht besonders.
Diese Komplexitätsklassen enthalten Sprachen, bei denen man sich für das Entscheidungsproblem interessiert. Liegt ein Element in einer Sprache oder nicht?
DTIME (POL) ist dann also die Menge der Sprachen, deren Charakteristische Funktion in Polynomzeit berechenbar ist.

Zu NTIME(POL): Die Vorstellung, dass ein Orakel im nichtdeterministischen Part die Lösung rät ist in Ordnung, aber etwas unexakt. Für eine spezielle Eingabe definiert man den Zeitverbrauch einer NDTM als MINIMALE Anzahl von Arbeitsschritten die bei einer akzeptierenden Berechnung ausgeführt werden. Betrachtet man alle Eingaben der gleichen Länge, wird die Maximale Laufzeit dieser Eingaben als Maß des Aufwandes genommen. Das ist imho wichtig, da man sich so von der zufallsbasierten Natur einer NDTM lösen kann.

Dann möchte ich dich noch auf eine Alternative Definition der Klasse NP hinweisen:

$NP = \{ L : \exists$ endliches Alphabet $\Sigma, L \subset \Sigma^* , \exists$ Polynom $p,$
$\exists$ Prädikat $Q \subset \Sigma^* \times \Sigma^* :$
$Q \in P, \forall x \in \Sigma^* :$
[ x \in L \iff \exists y \in \Sigma^* : ( |y| \leq p(|x|) , Q(x,y) ) ] \}

Das bedeutet:
Es gibt ein in Polynomzeit berechenbares Prädikat Q und ein x ist Element der Sprache L genau dann wenn es einen Zeugen y gibt (wobei der Zeuge polynomial längenbeschränkt ist in Abhängigkeit von x) und Q(x,y) gilt.

Beispiel SAT:
Eine Formel x in KNF sei erfüllbar und somit Element von SAT. Ein Zeuge y kodiert in irgendeiner Art und Weise eine Belegung der Variablen in x. Ob diese Belegung die Formel tatsächlich erfüllt ist in Polynomzeit entscheidbar. Das ist die Aufgabe des Prädikates Q.

Gruß, space

elise

ok. danke.

jetzt werde ich tief durchatmen und weiterlernen. sat kommt als nächstes.
damit hast du schon weiterreichend erklärt

kurz noch: "zeuge" ? dieses wort kenn ich nicht.
ich google mal ...

Man nennt dieses y einfach Zeugen, weil es die Zugehörigkeit von x zur Sprache gewährleistet, bezeugt, sichert...

elise

dank dir.
hab zu sehr eckig gedacht.

mein skript ist leider so mühsam, dass ich es alle 10 minuten in die ecke kicke und genervt gegen die wand trete.
(wenn ich richtige vorlesungen hätte, könnte ich wenigstens dem dozenten dumme fragen an den kopf knallen .. nur mit skripten halten sich die profs und dozis hervorragend bedeckt, keiner kann ihnen was...)

Kannst ja mal in mein altes Skript schauen:
http://www-ag-mayer.informatik.uni-kl.de/~agmlehre/ws03/eaa/

elise

thx, schau ich durch

ERROR

hi

hast schon den tu-berlin kram dazu angeguckt??

folie und "script"

nicht weltbewegend, aber eventuell hilfts ja:

http://tal.cs.tu-berlin.de/lv/ws0405/thegi1.html

ps: jaaaaaaaaaaaa erste semester ist geschaft

elise

danke

irgendwie ist mein eindruck, eure skripte enhalten viel viel text und weniger beweise... *neid*
meins besteht aus mathematischen angehauchten minimalsttexten und dann nur beweisen, beweisen, beweisen..

ist gut, mal was zu lesen