Изворни код странице NEXPTIME

У [[Теорија сложености|рачунарској теорији сложености]], [[класа сложености]] '''NEXPTIME''' , која се понекад назива '''NEXP''', је [[скуп]] [[Проблем одлучивања|проблема одлучивања]] који могу бити решени помоћу недетерминистичке Тјурингове машине коришћењем 2<sup>''n''<sup> [[Велико О|O]](1)</sup> </sup> времена и неограниченог простора. 
У терминима [[NTIME]],

:<math>\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(2^{n^k})</math>

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

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

Знамо да је:
:[[П (сложеност)|P]] <math>\subseteq</math> [[НП (класа комплексности)|NP]] <math>\subseteq</math> EXPTIME <math>\subseteq</math> NEXPTIME

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

:{{nbsp|2}} NP <math>\subsetneq</math> NEXPTIME{{nbsp|2}}

Ако је [[П = НП проблем|P = NP]], онда је NEXPTIME = EXPTIME (агумент попуњавања); тачније E ≠ NE ако и само ако постоје оскудни језици у '''NP''' који нису у '''P'''.<ref>Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. ''Information and Control'', volume 65, issue 2/3. стр. 158-181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</ref>

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

'''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 комплетности постиже „пројекцијом“)<ref>Christos Papadimitriou|C. Papadimitriou & Mihalis Yannakakis|M. Yannakakis, ''A note on succinct representations of graphs'', Information and control, vol 71 num 3, décember (1986). стр. 181—185, {{cite journal|doi=10.1016/S0019-9958(86)80009-2|pmc=|pmid=}}</ref><ref>C. Papadimitriou. ''Computational Complexity'' Addison-Wesley. {{page|year=1994|isbn=978-0-201-53082-7|pages=}} Section 20.1, pg.492.</ref>. Као један једноставан пример: овако постављено, проблем налажења [[Хамилтонов пут|Хамилтоновог пута]] за неки граф је '''NEXPTIME''' комплетан.

== Види још ==
* [[НП (класа комплексности)]]

== Референце ==
{{reflist}}

{{нормативна контрола}}

[[Категорија:Класе комплексности]]