- PVSM.RU - https://www.pvsm.ru -

NP-Complete

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


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

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

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

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

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

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

P = NP.

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

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

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

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

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

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

Через несколько минут, после смерти Маркуса и уничтожения компьютера, таинственная личность сверилась со своим портативным органайзером и тихо произнесла: «Леонид, код объекта — 10543, начало фазы мониторинга — через 2 дня».

Автор: emilmelnikov

Источник [1]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/kiberpank/71928

Ссылки в тексте:

[1] Источник: http://geektimes.ru/post/240362/