RE (комплексност)

У теорији израчунљивости и теорији коплексности израчунавања, RE (рекурзивно набројиво) је класа проблема одлучивања за које одговор „да“ може бити проверен Тјуринговом машином у коначном времену. Неформално, ово значи да ако је одговор на инстанцу проблема „да“, онда постоји нека процедура која за коначно време може да донесе ову одлуку, и која никад погрешно не одговара „да“, када је истинит одговор „не“. Међутим, када је истинит одговор „не“, од процедуре се не очекује да се заустави; за неке „не“ случајеве, може да уђе у „бесконачну петљу“. Оваква процедура се некад назива и семи-алгоритам, како би се разликовао од појма алгоритам, дефинисаног као комплетно решење проблема одлучивања.

Еквивалентно, RE је класа проблема одлучивања, за које Тјурингова машина може да излиста све одговоре „да“, један по један ( ово значи да је набројивост). Сваки члан RE је рекурзивно набројив скуп, а самим тим и Диофантов скуп. Слично, co-RE је скуп свих језика који су комплементарни језицима из RE. На неки начин, co-RE садржи језике чије се чланство може оповргнути у коначном временском периоду, док доказивање чланства може трајати заувек.

Везе са другим класама

Скуп рекурзивних језика (R) је је подскуп и RE и co-RE. У ствари, он је пресек ове две класе јер можемо да одлучимо било који проблем за који постоји препознавач и такође ко-препознавач, тако што ћемо их преплитати док један не дође до резултата. Одатле важи:

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

RE-комплетно

RE-комплетно је скуп проблема одлучивања који су комплетни за RE. На неки начин, ово су „најтежи“ рекурзивно набројиви проблеми. Сви овакви проблеми су нерекурзивни. Генерално се не усвајају никаква ограничења на коришћење редукције осим што оне морају бити м-редукције. Примери RE-комплетних проблема:

1. Проблем заустављања: Да ли ће програм, за коначан број улаза, зауставити рад или ће радити бесконачно.
2. По Рајсовој теореми ( Rice's Theorem), одлучивање о чланству за било који нетривијални подскуп скупа рекурзивних функција је RE-тешко. Оно ће бити комплетно кад год је скуп рекурзивно набројив.
3. Џон Мајхил (John Myhill) је доказао да су сви креативни скупови RE-комплетни.
4. Проблем униформне речи за групе и семигрупе. ( Заиста, проблем речи за неке индивидуалне групе је RE-комплетан.)
5. Одлучивање чланства у генералној формалној граматици без рестрикција. (Поново, одређене индивидуалне граматике имају RE-комплетан проблем чланства.)
6. Проблем пост-кореспонденције: За дати скуп стрингова, наћи да ли постоји стринг који може, дозвољавајући понављања, на два различита начина бити фкторисан у композицију стрингова.
7. Одређивање да ли Диофантова једначина има било које целобројно решење.
8. Проблем валидности логике првог реда.

Co-RE комплетно

co-RE комплетно је скуп проблема одлучивања који су комплетни за co-RE. На нјих се може рећи да су комплемент најтежих рекурзивно набројивих проблема. Примери co-RE комплетних проблема:

• Домино проблем за Ванг плочице (Wang tiles).
• Проблем задовољивости за логику првог реда.

Литература

• Korfhage, Robert R. (1966). Logic and Algorithms, With Applications to the Computer and Information Sciences. Wiley. стр. 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.”