КАК Я ВПЛОТНУЮ ПОДОШЁЛ К РЕШЕНИЮ ОДНОЙ ИЗ ПРОБЛЕМ ТЫСЯЧЕЛЕТИЯ

Практически никогда в жизни не терялся, за словом в карман не лез, даже если на мне была одёжка с карманами.

Но всё-таки в 1982 году был случай, когда растерялся и не знал, как реагировать. Это произошло, когда чинил лодочный мотор «Вихрь-25» в мастерской у личного мастера Валеры. И пока умелец по вихрям Валера асиливал неполадки, я коротал время в своём серийном катерке «Прогресс-2», причаленном к пристани мастерской. Рядом с лодками таких же терпельцев.

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

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

И этот стакан хозяин катерка и соответственно тамада застолья протянул мне. Я опять вежливо отказался. Тогда он вылил угощение мне в каюту. Вот тут я и растерялся: как реагировать? С одной стороны, человек меня угостил. С другой – вроде оскорбил. Тупиковая ситуация!

Я честно ему об этом сказал, на что он ответил такой же откровенностью. Типа, он и сам оказался в такой ситуации: угостил товарища по счастью предвкушения починенного мотора, а тот (то есть, я) отказался. Забрать обратно не мог, от себя и компашки уже оторвал, со стаканОм уже расстался. Но угощаемый его не принял, тогда ему пришлось вылить в каюту, чтобы по-скупердяйски не забирать взад.

Кароче, и у него, и у меня, то есть у нас, возникла нерешаемая проблема, которая, скорее относится к одной из нерешённых проблем тысячелетия - равенства классов P и NP. Которая формулируется примерно так: если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу NP, второго — классу P. Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов.

Когда я поведал моему соседу эту общечеловеческую проблему, он налил себе и мне по новому стакану, и мы выпили, чтобы повысить нашу сообразительность и всё-таки попытаться асилить проблему. Увы, не помогло... А жаль: за решение этой проблемы американский институт Клэя отстегнул бы приз в $1 лимон, и мы бы, в отличие от интилихента Перельмана, решившего одну из подобных задач тысячелетия, от этой суммы бы не отказались, честно поделив её на троих: моего собутыльника, меня и королевского пуделя белой масти Атоса Второго.
.