Verständnisfrage zur Komplexitätsklasse P
-
Hey Leute,
ich habe eine Frage zu Definition von P die uns so gegeben wurde: P = { A Teilmenge von N^k | XA ist Element von FP }.XA ist die charakteristische Funktion von A. FP sind die Funktionen die in polynomieller Zeit berechnet werden. Mein Problem ist jetz, A ist ja eine Menge von k-Tupeln z.B. A = { (1,2,3,4), (2,3,4,6), ..., (5,7,3,1) }.
Die charakteristische Funktion testet jetz jedes Element von N^k und gibt aus ob es in A liegt oder nicht und das in polynomieller Zeit. Im Internet steht jedoch das die Klasse P die Probleme sind die in polynomieller Zeit gelöst werden können? Was ist den jetz richtig, oder ist dass äquivalent?
MfG yihaaa
Edit: Uns wurde noch ein Beispiel gegeben { ( x, y, z ) | x^y = z } wäre ein Element von P. Warum?
-
yihaaa schrieb:
Die charakteristische Funktion testet jetz jedes Element von N^k und gibt aus ob es in A liegt oder nicht
nein, die Turingmaschine zur Berechnung der char. Funktion XA legt bei Eingabe *eines* beliebigen Wortes (sagen wir, x aus N^k oder einfacher x aus {0,1}^k) los und gibt nach höchstens polynomiell vielen Rechenschritten 1 (gdw x ist in A) oder 0 (gdw x ist nicht in A) aus.
anders gesagt: es gibt eine Konstante c>0, sodaß gilt: Hat das Eingabewort x die Länge |x|, dann braucht die Berechnung von XA auf Eingabe x höchstens |x|^c Schritte.
-
Ah habe ich mir schon so halb gedacht. Danke! Das mit dem N^k würde ja heißen was von der Form z.B. (x1, x2, ..., xk ) bei {0,1}^k wäre das ja dann z.B. (1,0,1,0) ist das dann als eine eingabe zu verstehen?
MfG
-
ja