Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «О СООТНОШЕНИИ КЛАССОВ СЛОЖНОСТИ МАШИН ТЬЮРИНГА, "Журнал вычислительной математики и математической физики"»

Авторы:
  • ЗАХАРОВ В.Н.1
  • Козмидиади В. А.2
стр. 730-743
Платно
1 Институт проблем комплексного освоения недр РАН, Москва, 2 ФИЦ ИУ РАН
Ключевые слова:
  • проблема "P vs NP"
  • "DSPACE(|X|) vs NSPACE(|X|)"
  • полиномиальная сводимость (сводимость по Карпу)
  • NP-полные машины Тьюринга
  • теория сложности вычислений
  • детерминированные машины Тьюринга
  • недетерминированные машины Тьюринга
Аннотация:
В работе определяются классы временной и пространственной сложности машин Тьюринга и рассматриваются соотношения между ними. Представлены также новые соотношения между введенными классами сложности. Библ. 13.

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.