Пить = Не Пить

Материал из Абсурдопедии
(перенаправлено с «П=НП»)
Перейти к навигации Перейти к поиску
WikiSU.png
Для людей с оригинально извращённым чувством юмора так называемые «эксперты» из Википедии предлагают статью под названием Равенство классов P и NP
Пить или не пить — вот в чём вопрос
~ Шекспир про пить или не пить

Пить = Не Пить (П = НП) — важнейшая задача современной неформатики. Формулируется она следующим образом: верно ли, что пьяный человек может сделать все то же, что и трезвый.

За доказательство или опровержение этой гипотезы Институт клея "Момент" обещает выдать миллион фиников и корову в придачу. Кроме того, если Пить действительно равно Не Пить, Урюпинское общество трезвости обещает выдать премию в размере 8 МРОТ, если это не получит огласки.

Наиболее вероятный путь доказательства гипотезы — предложить алкогоритм, как в пьяном виде выполнить одну из НП-жирных задач.

На данный момент неформатики-алкогоритмисты наклепали уже тучу таких задач, так что непонятно куда их теперь девать. К сожалению, мариновать их можно только при наличии экспоненциальной памяти, а консервировать не позволяет тезис Черча.

Примеры НП-жирных задач[править]

  • Задача о сумме (Задача SUM): сложить в уме два длинных числа.
  • Задача о коммивояжере (Задача PCOM): дан граф (частный случай: линия, прочерченная мелом на асфальте), требуется пройти по нему один раз, никуда не свернув.
  • Задача 3SAT: удовлетворить трех женщин за полиномиальное время.
  • Задача о клике (Задача CLIQUE): послать за бухлом максимальное число народа, чтобы они по дороге не набили друг другу морды.
  • Задача о минимальном покрытии (Задача MINCOVER): покрыть матом наименьшее число пьющих с тобой людей так, чтобы абсолютно все назвали тебя козлом.