NEXPTIME

У рачунарској теорији сложености, класа сложености NEXPTIME , која се понекад назива NEXP, је скуп проблема одлучивања који могу бити решени помоћу недетерминистичке Тјурингове машине коришћењем 2^{n O(1)} времена и неограниченог простора. У терминима NTIME,

${\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(2^{n^{k}})$

Алтернативно, NEXPTIME може бити дефинисана користећи детерминистичку Тјурингову машине као верификаторе. Језик L је у NEXPTIME ако и само ако постоје полиномијали p и q и детерминистичка Тјурингова машина M, таква да:

• За све x и y, машина M ради у времену 2^p(|x|) на улазу (x,y)
• За све x из L, постоји низ y дужине 2^q(|x|) тако да је M(x,y) = 1
• За све x који нису у L и све низове y of дужине 2^q(|x|) , M(x,y) = 0

Знамо да је:

P $\subseteq$ NP $\subseteq$ EXPTIME $\subseteq$ NEXPTIME

и на основу теореме о хијерархији времена да је:

   NP $\subsetneq$ NEXPTIME  

Ако је P = NP, онда је NEXPTIME = EXPTIME (агумент попуњавања); тачније E ≠ NE ако и само ако постоје оскудни језици у NP који нису у P.

Алтернативне карактеризације

NEXPTIME се обично појављује у контексту интерактивних система доказивања, где постоје две њене главне карактеризације. Први је MIP систем доказивања, где имамо два свемогућа доказивача који комуницирају са рандомизованим верификатором полиномијалног времена (али не и између себе). Ако је низ у оквиру језика, доказивачи морају да буду у стању да у то, са великом вероватноћом, убеде верификатора. Ако низ није део језика, доказивачи не смеју да буду у стању да заједнички преваре верификатора да прихвати низ, осим са малом вероватноћом. Чињеница да MIP системи доказивања могу да реше сваки проблем из NEXPTIME је прилично импресивна када узмемо у обзир да у случају када постоји само један доказивач, можемо само да распознамо цео PSPACE. Могућност верификатора да „унакрсно испитује“ два доказивача, даје му велику снагу. За више детаља, погледај интерактивни системи доказивања MIP. Други интерактивни систем доказивања који карактеризује NEXPTIME је извесна класа пробабилистички проверивих доказа. Подсетимо се да на NP може да се гледа као на класу проблема у којима свемогући доказивач даје наводни доказ да је низ у језику и детерминистичка полиномијална машина верификује да је доказ валидан. Направићемо следеће две измене у изнетој поставци:

• Машини за верификацију ћемо додати елемент случајности, могућност да се баци новчић.
• Уместо да једноставно предамо верификатору наводне доказе на траци, даћемо му могућност произвољног приступа. Верификатор може да специфицира индекс над доказним низом и прими одговарајући бит. Пошто верификатор може да упише индекс полиномијалне дужине, он потенцијално може да индексира експоненцијално дугачак доказни низ.

Ова два проширења заједно, значајно проширују снагу система доказивања и омогућава му да препозна све језике у NEXPTIME. Класа се зове PCP(poly, poly). Штавише, у овој карактеризацији, верификатор може да буде ограничен на читање константног броја битова, на пример NEXPTIME = PCP(poly, 1). За више детаља, погледај пробабилистички провериви докази.

NEXPTIME комплетност

Проблем одлучивања је NEXPTIME комплетан, ако се налази у NEXPTIME, и ако сваки проблем у NEXPTIME има полиномијално временско свођење типа више према један на њега. Другим речима, постоји алгоритам у полиномијалном времену, који трансформише инстанце једног у инстанце другог са истим одговором. Проблеми који су NEXPTIME комплетни могу да се сматрају најтежим проблемима у NEXPTIME. Знамо да NEXPTIME комплетни проблеми нису у NP. Теоремом о хијерархији времена, доказано је да ови проблеми не могу да се реше у полиномојалном времену. Значај скуп NEXPTIME комплетних проблема односи се на сажета кола. Сажета кола су једноставне машине које се користе за опис графова у експоненцијално мањем простору. Оне прихватају два броја чвора као улазни и излазни, ако постоји грана која их повезује. Ако решавамо проблем на графу у природној репрезентацији, као што је матрица повезаности, он је NP комплетан. Ако исти проблем решавамо помоћу репрезентације сажетог кола он је NEXPTIME комплетан, зато што је улаз експоненцијално мањи (под једним благим условом да се свођење NP комплетности постиже „пројекцијом“). Као један једноставан пример: овако постављено, проблем налажења Хамилтоновог пута за неки граф је NEXPTIME комплетан.

Види још

• НП (класа комплексности)