|
Доброго дня всем. Помогите, пожалуйста, решить две несложных задачки по теории вычислений.
1. Верно ли:
Если язык А принадлежит к NP классу, а нетривиальный язык Б к EXPTIME классу, то язык А полиномиально сводим к Б.
Я предложил такое решение - редукция недетерминистически за полиномиальное время проверяет принадлежность А к NP. Если да, то выводим на печать элемент, принадлежащий Б. Если нет, выводим на печать элемент, не принадлежащий Б. На что мне было сказано преподавателем, что редукция не может ничего решать недетерминистически.
2. Дан некоторый язык С. Язык Д определён как язык всех слов чётной длины в С. Показать, что существует такой NL полный язык С, что образованный из него язык Д не есть NL полный.
Единственный язык, который я знаю из книги Сипсера, что он NL полный - это язык PATH. Как можно показать, что все слова чётной длины из этого языка не есть NL полный язык, не знаю.
|
