[Recent Entries][Archive][Friends][User Info]
| September 23rd, 2013 | |
|---|---|
| 05:21 pm [Link] |     Есть программа длины n, которая на входе получает также n бит, а еще есть многочлен P. Вопрос: существует ли такой вход, что программа остановиться за P(n) шагов? Принадлежность задачи классу NP очевидна, докажем NP-полноту. Рассмотрим какую-нибудь задачу из NP, например задачу о Гамильтоновом цикле. Рассмотрим программу состоящую из: графа, получения информации, и выяснения, является ли полученная информация гамильтоновом циклом в этом графе. Если не является - хуячим бесконечный цикл. (в качестве P берем оценку сложности вычисления, чтения т д. - все полиномиально по определению NP) Вот. Заодно доказано, что NP-полные задачи вообще существуют (гораздо проще и понятнее, чем эта архаика с Вообще, предчувствую аналогию между невычислимыми задачами и соответствующими "задачами для бедных". Например, Колмогоровская сложность со времененем (правильно определенная) не должна быть полиномиально вычислима. Что значит, что у Колмогоровской сложности самая сильная невычислимость (http://www.youtube.com/watch?v=nnZPqnw Вообще нужно бороться за права заключенных и социализм вообще. Ну про Толокно все видели, а сегодня адвокат Стомахин рассказал всяких историй про то, как люди за деньги соглашаются получать условные сроки например. Грустно все это. МЫ ВСЕ ТАКИЕ ТРАГИЧЕСКИЕ ЛИЧНОСТИ ДАВАЙТЕ ЕБАТЬСЯ!!!!!! |