Proces eficient

Să fie dat o mulţime , unele dintre ale căror elemente au proprietatea . Atunci un proces eficient (metodă, algoritm ) este un astfel de proces care pentru orice element permite un număr finit de pași pentru a afla dacă elementul are sau nu o proprietate . $M$ $U$ $x \în M$ $X$ $U$

Proces semi-eficient

Dacă un element are proprietatea , un proces semi-eficient permite ca acest lucru să fie dezvăluit într-un număr finit de pași. Dacă nu are proprietatea , este posibil ca un proces semi-eficient să nu poată spune nimic precis într-un număr finit de pași. $X$ $U$ $X$ $U$ $X$

Astfel, printr-un proces semi-eficient, fie aflăm care are proprietatea, fie nu reușim să aflăm nimic despre . $X$ $U$ $X$

Vezi și

set rezolvabil
Decibilitatea algoritmică a teoriei formale.