Effektiv proces

Lad nogle sæt blive givet , nogle af hvis elementer har egenskaben . Så er en effektiv proces (metode, algoritme ) sådan en proces, der for ethvert element giver mulighed for et begrænset antal trin for at finde ud af, om elementet har en egenskab eller ej. $M$ $U$ $x \i M$ $x$ $U$

Semieffektiv proces

Hvis et element har egenskaben , gør en semi-effektiv proces det muligt at afsløre dette i et begrænset antal trin. Hvis den ikke har egenskaben , kan en semi-effektiv proces muligvis ikke sige noget bestemt om i et begrænset antal trin. $x$ $U$ $x$ $U$ $x$

Ved en semi-effektiv proces finder vi således enten ud af, at der har ejendommen , eller også finder vi ikke ud af noget om . $x$ $U$ $x$

Se også

løseligt sæt
Algoritmisk afgørelighed af formel teori.