В течение последних 2-3 лет равенство P и NP задач стало модным трендом, ведь мы дохуя близки к этому равенству, и каждый 4 псевдоматематик занимался подобной хуйней. Давайте рассмотрим, что это за задачи, как доказать (или опровергнуть) их равенство и что будет из этого следовать.

Для начала давайте рассмотрим историю Гаусса и его решение нахождения суммы чисел от 1 до 100. Нам не нужны всякие аспекты этого – оставим это историкам, нам важно, что это можно решить за довольно маленькое время, причём добавление новых элементов не сильно усложняет задачу, ведь у нас есть формула арифметической прогрессии – алгоритм. Так вот, раз и Гаусс, и учитель нашли ответ на эту задачу, то это можно считать задачей Р-типа. То есть имеющей алгоритм, который усложняется по формуле 2^log(n) – полиномиально (они решаются за это время на машине Тьюринга-Поста, где есть бесконечная разменянная лента, каретка, которая ставит между 2 разметок 1 и машина имеет 6 команд).

Однако, если бы учитель задал вопрос, на который Гаусс бы ответ не нашёл? Очевидно, что и сам учитель бы потратил бы больше времени на его решение. Допустим, это была задача, которую учитель подгонял под ответ, то есть алгоритма её решения нету, но можно решить проверкой – это задача NP-типа, – когда нам даётся неебически сложная задача, но её проверка займёт полиномиальное время.

Если ты не понимаешь (то ты конч), то давай рассмотрим пример: вы входите в заполненный рестик и ищите своего друга. Казалось бы – сотни или тысячи людей, его не найти, а если искать, то нужно осматривать каждого. Однако, если вам скажут: «Да это вон тот пидор», то вам нужно будет только проверить, но алгоритма быстрого решения вы найти не можете.

А теперь равенство. Как мы будем находить алгоритм для 2 задачи? «Хуем об косяк», – можете сказать вы, и это будет правильным вариантом, так как это сделать нереально. Возможно, нужно подойти к тому, что проверка – это и есть задача P-типа, но это не даёт равенства для NP-задач. Нам нужно каким-то неебически волшебным образом сделать итак, чтобы NP-задача сводилась в нихуя, превращаясь в задачу Р-типа. Например, вы можете попросить людей из 2 задачи разделиться на группы по 1 букве имени в алфавитном порядке, потом по 2 и так далее, пока вы не найдёте нужного человека – это один из вариантов решения, но это мы просто привели пример задачи NP-типа, сводящегося к P-типу, но если мы не можем попросить это сделать (то есть у нас нет дополнительных сведений), то это становится задача NP-типа. Но есть и NP-полные задачи, которые нельзя свести к P-задачам. Короче, смотрите картинку, я там более понятно расписал.

Равенство этой хуйни будет означать настоящий прорыв в математике, информатике, программировании, экономике и криптографии. Если это будет осуществлено, то конфиденциальность Гугла, Твиттера, Фейсбука, целой дохуищи банков пойдёт по пизде, так как мы поймём как разложить 2048 значное число на 2 простых множителя, но об этом в будущем, если вам будет интересно.



Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite