Back

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




                                     

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

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

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

                                     

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

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

R = RE ∩ co-RE. {\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}.}
                                     

2. RE-комплетно

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

  • По Рајсовој теореми Rices Theorem, одлучивање о чланству за било који нетривијални подскуп скупа рекурзивних функција је RE-тешко. Оно ће бити комплетно кад год је скуп рекурзивно набројив.
  • Одређивање да ли Диофантова једначина има било које целобројно решење.
  • Проблем пост-кореспонденције: За дати скуп стрингова, наћи да ли постоји стринг који може, дозвољавајући понављања, на два различита начина бити фкторисан у композицију стрингова.
  • Џон Мајхил John Myhill је доказао да су сви креативни скупови RE-комплетни.
  • Проблем заустављања: Да ли ће програм, за коначан број улаза, зауставити рад или ће радити бесконачно.
  • Проблем униформне речи за групе и семигрупе. Заиста, проблем речи за неке индивидуалне групе је RE-комплетан.
  • Одлучивање чланства у генералној формалној граматици без рестрикција. Поново, одређене индивидуалне граматике имају RE-комплетан проблем чланства.
  • Проблем валидности логике првог реда.
                                     

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

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

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