130
правок
Изменения
→Определение: добавил интервики на недетерминированные вычисления, обернул NP в ТеХ
|definition=<tex>\mathrm{NP}=\!\!\bigcup\limits_{p(n) \in poly}\!\!\operatorname{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых [[Недетерминированные вычисления|недетерминированной программой ]] за полиномиальное время.
{{Определение
|definition=<tex>\mathrm{coNP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}</tex>.
}}
То есть <tex>\mathrm{coNP}</tex> — это множество языков, дополнение к которым лежит в <tex>\mathrm{NP}</tex>.
{{Определение
|definition=<tex>\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in poly : x\in L\Leftrightarrow\exists y : |y|\le p(|x|), R(x,y)=1\}</tex>.
