Изменения

*'''DSPACE'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Space(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> &mdash; длина входа <tex>x</tex>.

Аналогичным образом введем классы '''[[NSPACE]]''' и '''[[NTIME]]''', использующие недетерминированную машину Тьюринга взамен детерминированной(в течении всего курса префикс '''D''' соответствует детерминизму, а '''N''' &mdash; недетерминизму).

*Класс '''P''' — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально: *'''P'''=<tex>\bigcup_{i=0}^{\infty}</tex>'''[[DTIME]]'''<tex>(in^i)</tex>*В свою очередь, при разрешении языка из класса '''NP''' используется недетерминированная машина: *'''NP'''=<tex>\bigcup_{i=0}^{\infty}</tex> '''NTIME'''<tex>(in^i)</tex>Дадим определение класса '''NP''' на языке сертификатов*'''NP'''=<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex> (Первое равенство доказывается в статье '''[[NP]]''')