Последнюю неделю я читаю 120-страничный
обзор текущего состояния проблемы
P =? NP. Для целей поста достаточно сказать, что это два класса(множества) вычислительных задач, про которые точно известно, что
NP содержит
P, но неизвестно, является ли это включение строгим. Т.е. есть ли задача из класса
NP, которая при этом не содержится в
P. Для желающих под спойлером чуть более подробное объяснение, но всё равно нестрогое и "на пальцах".
Рассмотрим задачу умножения двух N-битовых чисел (т.е. из N знаков в двоичной системе). Она легко решается умножением "столбиком" приблизительно за N^2 операций. Компьютер справится с этим умножением за доли секунды хоть при N=100, хоть при N=1000.
А теперь рассмотрим обратную задачу. Дано число
N из 200 битов. Известно, что N=k*m, где
k и
m - простые, и нужно эти два числа найти. Или другими словами, нужно найти число, на которое
N будет делиться. Самый наивный алгоритм, который проверит все возможные числа из 100 битов (этого достаточно, чтобы найти наименьшее из
k и
m), потребует 2^100 делений. Пожалуй, для
последнего вопроса можно придумать что-нибудь поважнее. В общем случае сложность перебора растёт как 2^N, и это называется экспоненциальной сложностью.
Конечно, есть более эффективные алгоритмы, но тем не менее способ по-настоящему "быстрого" решения второй задачи неизвестен, и на этом держится вся современная криптография.
При этом обратите внимание, что проверка конкретного ответа (что два конкретных числа
k и
m дают при умножении
N) - это наша первая задача, которая решается за доли секунды.
Теперь можно сформулировать, что такое классы P и NP.
P - это класс задач, для которых мы можем быстро
найти ответ.
NP - это класс задач, для которых мы можем быстро
проверить какой-то ответ на правильность. (При этом рассматриваются задачи, которые в принципе решаются полным перебором). Понятно, что если задача принадлежит классу
P, то она принадлежит и
NP. (Для проверки ответа
Y мы в крайнем случае можем найти правильный ответ
Х и сравнить его с
Y). Но пока неизвестно, равны эти классы или нет, P<NP или P=NP.
Если кто-то неожиданно заинтересовался
, можете задавать вопросы :)
В обзоре рассматриваются некоторые методы, с помощью которые математики пытались решить проблему, и полученные результаты. Также для большинства методов автор показывает, почему с их помощью невозможно доказать или опровергнуть, что P<NP. Казалось бы, как это вообще возможно -
доказать, что какой-то набор методов в принципе не может ответить на поставленный вопрос? Концепция доказательства очень красивая, поэтому я и решил ей поделиться.
Вместо классов
P и
NP рассматриваются
семейства классов P(x) и NP(x), где
x - некий объект. Т.е. для каждого объекта
x строится "своя" пара классов P(x) и NP(x). Затем показывается, что изучаемый набор методов "нечувствителен" к значению
x - любые результаты, верные при
x1, будут верны и при любом другом
x2. После этого находятся конкретные
x1 и
x2 такие, что
P(x1)=NP(x1), но
P(x2) < NP(x2). Иными словами, показывается, что если данные методы "докажут" (не)равенство P и NP, то они так же "докажут" это и в тех случаях, когда это неверно!
Мне кажется, что это очень полезный навык в логическом мышлении - спрашивать себя, могу ли я использовать тот же ход рассуждений для доказательства очевидно неверного тезиса. Если помните, я говорил про свою главную претензию к феминизму, которая как раз в том, что используемые им аргументы неспособны отличить бокс от медицины.
Я вспомнил об этом, когда думал о влиянии субсидий на экономический рост. У меня там как раз возник момент, когда рассуждения приводили к одному и тому же результату там, где он должен быть разным - вечером напишу об этом. А пока в качестве примера такой ход рассуждений: "Латвия каждый год получает субсидии в размере 5% от годового ВВП. Поскольку годовой рост в 5% - это очень много, значит такие субсидии вносят в общий рост Латвии огромный вклад".
Можно заметить, что это рассуждение нечувствительно к выбору единицы измерения времени. Заменим год на месяц. Субсидии в 5% от годового ВВП каждый год - это то же самое, что 5% от месячного ВВП каждый месяц. Получаем: "Латвия каждый месяц получает субсидии в размере 5% от месячного ВВП. Поскольку месячный рост в 5% - это..." - и далее по тексту. Таким способом можно обосновать огромный вклад от субсидий и в 0,5%, и в 0,1% - надо только правильно выбрать период времени для сравнения.
Конечно, нужно не путать такой приём с доведением до абсурда, когда вместо типичного случая в рассуждение специально подставляется крайнее исключение. "Ты против пыток арестованных, но представь, что это террорист, который спрятал атомную бомбу и не говорит, где она". Однако в приведённом рассуждении единицы времени в 1 год и в 1 месяц действительно равноправны.
1. Я НИГДЕ не говорил про 5% роста ВВП от субсидий. Я только отметил что что бы то ни было в размере 5% от ВВП это порядком дохера.
2. Если тебе иностранная помощь приходит каждый год (а она приходит каждый год), то не один раз, да?
3. Но главное. Объясни мне, как человек со специальностью мировая экономика, чем получение субсидий в размере Х евро отличается от производства уникального товара с добавочной стоимостью в Х евро и продажей его за рубеж?