Пить = Не Пить

Пить или не пить — вот в чём вопрос

~ Шекспир про пить или не пить

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

Задача вперыве сформулирована и доказана бухломатиком Фома на ферме приусадебного хозяйства в 3716 году вместо нашей эры. Доказательство было написано (и накакано) на полях нашей необъятной страны и там же утеряно после внесения осеннего навоза. По словам самого Фомы доказательство настолько длинно, что ему не хватило поля для полного изложения всего его содержимого.

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

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

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

Примеры НП-жирных задач:

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