|
>AbsurdopediaMovedTo Absurdopedia.Net |
| Строка 1: |
Строка 1: |
| {{wikipedia|Равенство классов P и NP}}
| | <noinclude><table cellpadding=0 cellspacing=0 style="border: 1px dotted black; border-left: none; position: absolute; z-index: 99;"><td valign=center width=1% style="background-color: #ff6060; color: #ffffff; font-family: Old English Text MT; font-size: 50px; font-weight: bold;" title="Уведомление"> ! </td><td style="padding: 23px 6px 20px 6px; font-size: 120%;"><b>Абсурдопедия переехала и теперь находится по адресу [[:pt:ru:Заглавная_страница|absurdopedia.net]].</b><br />См. [[:pt:ru:{{PAGENAME}}|http://absurdopedia.net/wiki/{{PAGENAME}}]]</td></table><hr /></noinclude> |
| {{q|Пить или не пить — вот в чём вопрос|Шекспир|пить или не пить|nolink=1}}
| |
| Пить = Не Пить (П = НП) — важнейшая задача современной неформатики. Формулируется она
| |
| следующим образом: верно ли, что пьяный человек может сделать все то же,
| |
| что и трезвый.
| |
| | |
| За доказательство или опровержение этой гипотезы [[Институт клея "Момент"]] обещает выдать миллион фиников и корову в придачу.
| |
| Кроме того, если Пить действительно равно Не Пить, [[Урюпинское общество трезвости]] обещает выдать премию в размере 8 [[Абсолютный Нуль|МРОТ]], если это не получит огласки.
| |
| | |
| Наиболее вероятный путь доказательства гипотезы — предложить алкогоритм, как
| |
| в пьяном виде выполнить одну из НП-'''жирных''' задач.
| |
| | |
| На данный момент неформатики-алкогоритмисты наклепали уже тучу таких задач,
| |
| так что непонятно куда их теперь девать. К сожалению, мариновать их можно
| |
| только при наличии экспоненциальной памяти, а консервировать не позволяет
| |
| тезис Черча.
| |
| | |
| == Примеры НП-'''жирных''' задач == | |
| * Задача о сумме (Задача SUM): сложить в уме два длинных числа.
| |
| * Задача о коммивояжере (Задача PCOM): дан граф (частный случай: линия, прочерченная мелом на асфальте), требуется пройти по нему один раз, никуда не свернув.
| |
| * Задача 3SAT: удовлетворить трех женщин за полиномиальное время.
| |
| * Задача о клике (Задача CLIQUE): послать за бухлом максимальное число народа, чтобы они по дороге не набили друг другу морды.
| |
| * Задача о минимальном покрытии (Задача MINCOVER): покрыть матом наименьшее число пьющих с тобой людей так, чтобы абсолютно все назвали тебя козлом.
| |
| | |
| {{stub|reason=Возможно, автор выбрал первый вариант.}} | |
| {{Математика}} | |
| [[Категория:Математика]]
| |
| [[Категория:Наука]]
| |
| [[Категория:Шутки для посвящённых]]
| |