Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия |
Ваш текст |
| Строка 10: |
Строка 10: |
| | | | |
| | 2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex> | | 2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex> |
| − |
| |
| − | Будем строить B такое, чтобы для всех М.Т. из Р с оракулом С, данная машина тьюринга "ошибалась" на входе некоторой длины, при ответе на вопрос, есть ли в B слово той же длины, что и вход.
| |
| − |
| |
| − | Положим множество B пустым.
| |
| − | 1. Переберем все машины тьюринга. Их счетное множество, каждая работает за полином.
| |
| − | 2. Для текущей МТ найдем первую длину i, такую что для всех слов длины не менее i ни одна из уже отработавших МТ ничего не спрашивала про них у оракула.
| |
| − | 3. Опишем поведение подходящего оракула. Пусть, если МТ М запущена на длине i, и задает вопросы оракулу C. Если М спросит С про слово длины не менее i, С должен ответить 0, одновременно запомнив, что это слово никогда не должно оказаться в В. Если же М спросит про уже включенные в В слова, С должен ответить 1.
| |
| − | 4. Теперь заметим, что так как М работает за полином, а ни про одно слово из i ничего не известно, то М не успеет спросить про все слова длины i, их экспоненциальное количество, значит будет хотя бы одно слово длины i, про которое М не спросит. Теперь, если М ответит 1, то нужно чтобы в В не было ни одного слова длины i, иначе - добавим в B первое в лексикографическом порядке слово из В длины i, про которое М не спрашивала.
| |
| − | 5. вернемся на шаг 1.
| |
| − |
| |
| − | готово, построено множество слов В, такое что ни одна машина тьюринга из P с оракулом не сможет разрешить, но очевидно, что это множество из NP с оракулом
| |
