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


Log in to reply