Все слова языка L принимаются машиной Тьюринга M за полиномиальное время, и ни- какие другие слова машиной M не принимаются (но, возможно, и не отвергаются). Верно ли, что L лежит в P?

задан 21 Май '17 23:04

А что на этот счёт говорят определения? :)

(22 Май '17 0:20) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×243

задан
21 Май '17 23:04

показан
321 раз

обновлен
22 Май '17 0:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru