NP-Complete

Короткий рассказ, придуманный накануне mid-term по Algorithms and Data Structures вместо повторения лекций.



Ещё раз проверив свои выкладки, Маркус не поверил своим глазам. То, что у него получилось, просто обязано было быть ошибкой. В конце-концов, тысячи учёных пытались исследовать эту проблему и в итоге так ничего и не добились.

Решительно настроенный обнаружить недочёт в своих рассуждениях, Маркус за несколько десятков минут написал алгоритм по своим теоретическим построениям, преисполненный уверенности. Реальное применение его теории точно даст неверный ответ. Что же ещё может пролить свет на его ошибки, как не прямая реализация его метода на реальной вычислительной машине?

После нескольких мелких ошибок компиляция прошла успешно. Забыв обо всём на свете, Маркус целую минуту не решался запустить программу. «Что же будет, если она будет работать, если прямо здесь и сейчас выдаст верный ответ?» — думал он. Наконец, убедив себя, что это просто невозможно, Маркус нажал нужную клавишу и тут же, испугавшись, закрыл глаза.

Через минуту, отважившись взглянуть на монитор, он долго, невидящим взглядом смотрел на число, напечатанное программой в консоли. «Что за гнусный день? Может, я сплю?» — думал Маркус, уставившись на ярко горящие в ночной тьме пиксели своего старенького монитора.

Оправившись от оцепенения, он тут же взялся за отладчик, преисполненный решимости найти ошибку в своей программе. В самом деле, не может же быть, чтобы в его программе не было каких-то ошибок. Очень редко удаётся написать алгоритм сразу и без багов, да ещё и в третьем часу ночи, проведя несколько часов без чашки кофе.

И всё-таки, раз за разом, отслеживая свой алгоритм, Маркус всё больше убеждался в том, что он смог найти невероятный по своей значимости и простоте метод, который буквально перевернёт мир с ног на голову. Он смог доказать то, что другие уже давно перестали рассматривать как актуальную научную проблему.

P = NP.

Чтобы окончательно убедить себя, Маркус принялся писать набор тестов, которые решали NP-полные проблемы для небольших входных данных по классическим переборным алгоритмам и его новому методу. В конце вычислений значения сравнивались, и если хоть одно решение не совпадало, тесты считались неудачными.

Запустив тесты и зная, что на его машине результатов придётся ждать около 10 минут, Маркус пошёл на кухню, чтобы выпить ещё кофе: ночь обещала быть долгой. С трудом дождавшись вскипевшего чайника, он сварил себе напиток и с чашкой бодрящего зелья направился обратно к компьютеру.

Увидев человека в чёрном в своём кресле рядом с компьютером, Маркус не испугался: он был слишком взволнован и слишком измотан, чтобы бояться. Он всего лишь спросил: «Кто вы? Что вы здесь делаете?», словно к нему в квартиру каждый день забирались незнакомые люди.

«Я — просто тот, кому поручено исполнять приказы и устранять проблемы.» — ответила фигура в чёрном — «Несмотря на то, что мне приходится делать по долгу службы, я никогда не перестаю восхищаться людьми, подобными вам. Очень жаль, что нам приходится встречаться в такой ситуации».

Ещё заваривая свой кофе на кухне, Маркус почувствовал некоторую слабость. Тогда он списал это на физическое и эмоциональное истощение. Теперь же он ясно понимал, чем было вызвано его состояние. Не в силах предпринять что-либо ещё, он смог задать единственный вопрос, волнующий его больше всего: «Почему?». Чёрный человек грустно вздохнул и ответил: «А как вы сами думаете? Охрана инвестиций. Банки. Правительство. Что же ещё это может быть?».

Маркус начал терять равновесие. Незнакомец подхватил его, уложил на кровать, накрыл одеялом и произнёс: «И снова исчезли сегодня грандиозные открытия, но также исчезли и грандиозные потрясения. Общество только выиграло. Поверьте мне, я знаю, я это видел.»

Через несколько минут, после смерти Маркуса и уничтожения компьютера, таинственная личность сверилась со своим портативным органайзером и тихо произнесла: «Леонид, код объекта — 10543, начало фазы мониторинга — через 2 дня».
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 20

    –5
    P=1 или N=0.
      +3
      Наоборот.
        +2
        Это при условии, что P=NP :)
      +1
      А давайте немного похоливарим!
      Мне вот инетересно а действительно ли равенство классов повличет за собой последствия для «Охраны инвестиций. Банков. Правительства.».
      Ну докажут что задачи класса NP также легко решить, как и проверить решение. Но обязательно ли доказательство будет содержать ключ к решению NP-задач?
      И вообще, вся эта суета с P=NP в основном связана с современной криптографией. Но ведь с классификацией факторизации больших чисел математики так и не определились (поправьте если я не прав), и до сих пор неясно к какому классу относится эта задача. Раз мы не уверены в принадлежности задачи факторизации к классу NP, то следовательность, на мой взгляд, доказательство равенства P=NP для задачи факторизации не будет иметь особого значения.
        0
        Принадлежность задачи факторизации классу NP не вызывает никаких сомнений. Сомнения вызывает принадлежность (точнее, непринадлежность) этой задачи классу P.
          0
          Вы правы, я все перепутал.
          И тем не менее это, как мне кажется, еще не делает равенство P=NP криптокатастрофой.
            +1
            В общем случае оно, конечно же, сильно зависит от оценки времени — но если там выходит порядка n10 операций для факторизации числа — то это все равно значительно быстрее, чем image (оценка времени для общего метода решета числового поля, n — число разрядов) уже при n=1024.

            А к чему приведет быстрый алгоритм факторизации больших чисел — объяснять, думаю, не надо.

            Эллиптическая криптография не спасет — из-за малой длины ключа она, скорее всего, пострадает в первую очередь.
              0
              Спасибо, как раз об этом и хотел написать. Но ведь может быть как раз таки и наоборот. Т.е. для NP задач будут найдены полиномиальные алгоритмы решения, но степень полинома может быть настолько большой, что это не приведет к потере стойкости асимметричных криптосистем. Да конечно такое доказательство будет сигналом к тому что пора отказываться от криптографии в текущем ее состоянии, но при этом такое развитие событий не дает повода для паники.
              И кстати, не знаете рассматривается ли возможность доказательства без предоставления полиномиального решения одной из NP-полных задач?
                0
                Не знаю.
                  +2
                  Известен алгоритм, который решает NP-полную задачу и работает полиномиальное время, если P=NP. Так что не рассматривается.
          0
          Зачем убивать Маркуса? Можно же придумать что-то вроде стирания памяти.
          Пример
            +1
            А что, если это изобретение тоже из разряда «переворачивающих мир»?
              0
              На самом деле так и было, они же не изверги какие-то.
              А нам сказали, что Маркус мёртв, чтобы не повадно было алгоритм искать.
                +3
                Позволил себе немного переписать текст, чтобы было менее кровожадно :)

                «TRUE»
                Придя в себя от первого шока, Маркус взяглянул на часы. Было почти пять утра. Не даром у него так сильно слипались глаза. «Так, надо пойти и заварить себе кофе, а то усну на работе», — сказал он сам себе. Маркус, протерев глаза и хорошенько потянувшись, поднялся с кресла и пошел на кухню. Воды в чайнике не оказалось, емкость с фильтром также была пуста, поэтому он набрал чайник из-под крана, затем, немного подумав, сунул голову под струю ледяной воды. Спать расхотелось моментально. Наскоро вытерев голову полотенцем и поставив чайник на газ, он почти бегом бросился к столу.
                Ещё раз проверив свои выкладки, Маркус не поверил своим глазам. То, что у него получилось, просто обязано было быть ошибкой. В конце-концов, тысячи учёных пытались исследовать эту проблему и в итоге так ничего и не добились.

                Решительно настроенный обнаружить недочёт в своих рассуждениях, Маркус за несколько десятков минут написал алгоритм по своим теоретическим построениям, преисполненный уверенности. Реальное применение его теории точно даст неверный ответ. Что же ещё может пролить свет на его ошибки, как не прямая реализация его метода на реальной вычислительной машине?

                После нескольких мелких ошибок компиляция прошла успешно. Забыв обо всём на свете, Маркус целую минуту не решался запустить программу. «Что же будет, если она будет работать, если прямо здесь и сейчас выдаст верный ответ?» — думал он. Наконец, убедив себя, что это просто невозможно, Маркус нажал нужную клавишу и тут же, испугавшись, закрыл глаза.

                Через минуту, отважившись взглянуть на монитор, он долго, невидящим взглядом смотрел на «TRUE», напечатанное программой в консоли. «Что за гнусный день? Может, я сплю?» — думал Маркус, уставившись на ярко горящие в ночной тьме пиксели своего старенького монитора.

                Оправившись от оцепенения, он тут же взялся за отладчик, преисполненный решимости найти ошибку в своей программе. В самом деле, не может же быть, чтобы в его программе не было каких-то ошибок. Очень редко удаётся написать алгоритм сразу и без багов, да ещё и в пять утра, проведя несколько часов без чашки кофе.

                И всё-таки, раз за разом, отслеживая свой алгоритм, Маркус всё больше убеждался в том, что он смог найти невероятный по своей значимости и простоте метод, который буквально перевернёт мир с ног на голову.

                Он смог доказать то, что другие уже давно перестали рассматривать как актуальную научную проблему.

                P = NP.

                Чтобы окончательно убедить себя, Маркус принялся писать набор тестов, которые решали NP-полные проблемы для небольших входных данных по классическим переборным алгоритмам и его новому методу. В конце вычислений значения сравнивались, и если хоть одно решение не совпадало, тесты считались неудачными.

                Теперь они были запущены, а Маркусу оставалось только ждать.

                На кухне пронзительно засвистел чайник. Маркус вздрогнул и побежал его выключать. На столе стояла чашка с кофе, и его запах уже был по всей кухне. Маркус залил кофе кипятком, добавил пять ложек сахара «для улучшения работы мозга», размешал и осторожно хлебнул. На вкус кофе было сносным, но был явный перебор с сахаром.

                Маркус хлебнул еще раз и пошел к себе в комнату.

                Увидев человека в чёрном в своём кресле рядом с компьютером, Маркус не испугался: он был слишком взволнован и слишком измотан, чтобы бояться. Он всего лишь спросил: «Кто вы? Что вы здесь делаете?», словно к нему в квартиру каждый день забирались незнакомые люди.

                Человек отвлекся от монитора, быстро взглянул на Маркуса через плечо и бросил:«Сядьте». Маркус чуть не выронил чашку:«Это вообще-то моя кв...». «Я сказал вам сесть», — перебил его человек. Маркус сел и отхлебнул в третий раз. Незнакомец повернулся к нему, достал телефон и, не сводя с Маркуса взгляд, сказал в трубку:«Два, семь, пять, восемнадцать. Проблему подтверждаю. Подкрепления не потребуется.» От этих слов у Маркуса пересохло во рту. «Как хорошо, что кофе со мной», — подумал он.
                Человек тем временем закончил разговор и убрал телефон.
                — Меня зовут Пол. Ваша работа? — он ткнул пальцем в монитор через плечо. В консоли была надпись «TRUE», означающая что написанные тесты сошлись.
                — Нет, монитор собирал не я — пошутил Маркус.
                — Остроумно, — поморщился Пол. — Вы тугодум и мне повторить свой вопрос?
                — Нет, не надо — покраснел Маркус. Пол не мигая смотрел на него
                — Видимо, все же придется повторить. Ваша работа?
                — Да, я автор — Маркус покраснел еще сильнее.
                — Замечательно. Согласно статье 23, ваше открытие подлежит изъятию. Заранее предупреждаю, что все уже решено, а если бы вы и могли оказать сопротивление, оно бы только усугубило ситуацию.
                — Я против и могу оказать его!
                — Очень сомневаюсь.
                — В смыс… — только сейчас Маркус понял, что он кофе в чашку не насыпал. Веки вдруг стали свинцовыми — Кофе!
                — Быстро вы поняли. Не бойтесь, это не больно. Я оставлю вам свою визитку, нам нужны такие люди.
                Но Маркус уже спал.

                Маркус открыл глаза и посмотрел на часы. Было почти шесть утра. На мониторе в консоли было написано «FALSE». «Что и следовало ожидать. Видимо, я все-таки ошибся в расчетах», подумал Маркус, «Как же болит голова, не надо было сидеть полночи, а еще и засыпать за компьютером. Еще и ерунда какая-то приснилась».

                Он выключил компьютер и уже собирался выключить настольную лампу, как увидел небольшой прямоугольник из белого картона. На нем был незнакомый номер телефона и всего одно слово. «Пол».

                И неожиданно Маркус все вспомнил.

                  0
                  Так не пойдёт, ибо нет гарантии что он не повторит и не опубликует доказательство. Понятно что он «под колпаком», но риск для спецслужб слишком велик.
                  +2
                  Конечно. Маркус уже давно работает на нас, в секретном бункере, в котором он проведёт остаток своей жизни.
                  Рассказ же заканчивается именно так, чтобы больше никто не помышлял искать решение.

                  GLORY TO ARSTOTZKA
                    0
                    Предположу, что если бы просочилась информация, что спецслужбы устраняют математиков, решивших P=NP, то это бы ни разу не остановило бы остальных, наверняка бы даже подхлестнуло массовые поиски доказательства. Запугивание никогда не было и не может быть долгосрочным эффективным методом.
                      +1
                      Понятно, зачем здесь этот расказ :)
                      Его оставила албанская спецслужба, у которой не хватает ресурсов на брутфорс и срочно нужно решение этой проблемы.
                      0
                      Now I have passport!
                  0
                  Фильм был с похожим сюжетом, кстати: Travelling Salesman. Ничего из рядо вон выходящего, но на раз посмотреть вполне сгодится.

                  Only users with full accounts can post comments. Log in, please.