RE (kompleksnost)

U teoriji izračunljivosti i teoriji kopleksnosti izračunavanja, RE (rekurzivno nabrojivo) je klasa problema odlučivanja za koje odgovor „da“ može biti proveren Tjuringovom mašinom u konačnom vremenu. Neformalno, ovo znači da ako je odgovor na instancu problema „da“, onda postoji neka procedura koja za konačno vreme može da donese ovu odluku, i koja nikad pogrešno ne odgovara „da“, kada je istinit odgovor „ne“. Međutim, kada je istinit odgovor „ne“, od procedure se ne očekuje da se zaustavi; za neke „ne“ slučajeve, može da uđe u „beskonačnu petlju“. Ovakva procedura se nekad naziva i semi-algoritam, kako bi se razlikovao od pojma algoritam, definisanog kao kompletno rešenje problema odlučivanja.

Ekvivalentno, RE je klasa problema odlučivanja, za koje Tjuringova mašina može da izlista sve odgovore „da“, jedan po jedan ( ovo znači da je nabrojivost). Svaki član RE je rekurzivno nabrojiv skup, a samim tim i Diofantov skup. Slično, co-RE je skup svih jezika koji su komplementarni jezicima iz RE. Na neki način, co-RE sadrži jezike čije se članstvo može opovrgnuti u konačnom vremenskom periodu, dok dokazivanje članstva može trajati zauvek.

Veze sa drugim klasama

Skup rekurzivnih jezika (R) je je podskup i RE i co-RE. U stvari, on je presek ove dve klase jer možemo da odlučimo bilo koji problem za koji postoji prepoznavač i takođe ko-prepoznavač, tako što ćemo ih preplitati dok jedan ne dođe do rezultata. Odatle važi:

${\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}.$

RE-kompletno

RE-kompletno je skup problema odlučivanja koji su kompletni za RE. Na neki način, ovo su „najteži“ rekurzivno nabrojivi problemi. Svi ovakvi problemi su nerekurzivni. Generalno se ne usvajaju nikakva ograničenja na korišćenje redukcije osim što one moraju biti m-redukcije. Primeri RE-kompletnih problema:

1. Problem zaustavljanja: Da li će program, za konačan broj ulaza, zaustaviti rad ili će raditi beskonačno.
2. Po Rajsovoj teoremi ( Rice's Theorem), odlučivanje o članstvu za bilo koji netrivijalni podskup skupa rekurzivnih funkcija je RE-teško. Ono će biti kompletno kad god je skup rekurzivno nabrojiv.
3. Džon Majhil (John Myhill) je dokazao da su svi kreativni skupovi RE-kompletni.
4. Problem uniformne reči za grupe i semigrupe. ( Zaista, problem reči za neke individualne grupe je RE-kompletan.)
5. Odlučivanje članstva u generalnoj formalnoj gramatici bez restrikcija. (Ponovo, određene individualne gramatike imaju RE-kompletan problem članstva.)
6. Problem post-korespondencije: Za dati skup stringova, naći da li postoji string koji može, dozvoljavajući ponavljanja, na dva različita načina biti fktorisan u kompoziciju stringova.
7. Određivanje da li Diofantova jednačina ima bilo koje celobrojno rešenje.
8. Problem validnosti logike prvog reda.

Co-RE kompletno

co-RE kompletno je skup problema odlučivanja koji su kompletni za co-RE. Na njih se može reći da su komplement najtežih rekurzivno nabrojivih problema. Primeri co-RE kompletnih problema:

• Domino problem za Vang pločice (Wang tiles).
• Problem zadovoljivosti za logiku prvog reda.

Literatura

• Korfhage, Robert R. (1966). Logic and Algorithms, With Applications to the Computer and Information Sciences. Wiley. str. 89. „A method of solution will be called a semi-algorithm for [a problem] P on [a device] M if the solution to P (if one exists) appears after the performance of finitely many steps. A semi-algorithm will be called an algorithm if, in addition, whenever the problem has no solution the method enables the device to determine this after a finite number of steps and halts.”