avva | математическо-политическое

Важность вопроса P?=NP напрямую связана с эффективностью пыток.

Вопрос P?=NP важен потому, что так много сложных задач - не только в информатике, но и в других разных науках - которые мы не умеем эффективно решать, относятся к классу NP. Это значит, что если есть вариант решения, то проверить, правильное это решение или нет, можно очень быстро; но найти правильное решение - очень тяжело и требует слишком много времени и сил.

Предположим, на острове закопано сокровище, а у вас есть лопата, и вы хотите его найти. Если вам кто-то даст карту, на которой отмечено крестиком нужное место, то проверить этот "вариант решения" довольно просто - пойти туда и попробовать копать. Но если карты у вас нет, то найти нужное решение тяжело - неясно, что можно сделать, кроме как перекопать весь остров (если у вас нет дополнительной информации).

Если окажется, что P=NP (во что мало кто верит), это будет значить, в предложенной аналогии, что каким-то странным и непонятным образом можно будет найти клад, не копая всюду, всего за несколько попыток, пользуясь только тем, что одну отдельную попытку можно сделать быстро. Казалось бы, это очевидный бред, но, наверное, не очень очевидный, раз доказать обратное - что P не равно NP - тоже никому не удается уже сорок лет.

О пытках часто говорят, что они неэффективны, потому что подвергающиеся пыткам люди говорят то, что хотят услышать пытчики, а вовсе необязательно правду. Что если они не знают правду, то будут говорить наобум, чтобы прекратили пытки. Итп. В какой-то степени это верно, но в какой точности, я не знаю. Подозреваю, что многие из таких утверждений основаны на идеологической убежденности, а не на фактах или опыте. Так как я в любом случае считаю, что пытки недопустимы и должны быть запрещены, мне не очень важно разбираться в этом вопросе.

Но если все же задуматься об этом, то видим, что даже если все, что говорят о ложных и неточных ответах, о "говорят то, что хотят услышать пытчики" - даже если все это верно, это необязательно показывает неэффективность пыток. Суть в том, что вопросы, ответы на которые ищут с помощью пыток, часто оказываются NP-задачами: предполагаемый ответ легко проверить. Предположим, мы поймали 20 пиратов, которые когда-то имели отношение к этому острову, и, возможно, даже к спрятанному сокровищу (мы не знаем точно; у нас есть всякие косвенные свидетельства, а сами пираты все отрицают, естественно). Мы их всех пытаем с целью узнать, где клад. Часть пиратов ничего не скажет под пытками. Кто-то, может, умрет от них. Кто-то ничего не знает, но будет говорить наугад, только бы перестали пытать. Кто-то, может, знает, но скажет неверное место. Но все это не очень важно, потому что мы так легко может проверить любой вариант - просто послать пару человек с лопатой в это место на пару часов. Если мы получили десять вариантов, и только один из них на самом деле верный - ничего страшного, перепробуем все десять и найдем клад. А если ни один не оказался верным - что ж, будем пытать дальше или еще пиратов искать. Если действительно есть пираты, которые знают, где клад, и у нас есть шанс их поймать, то очень может быть, что в итоге мы обнаружим сокровище, и значит, пытки в этом случае окажутся эффективным методом.

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

Очень многие практические проблемы в окружающем мире устроены подобно NP-задачам. Это обстоятельство одновременно демонстрирует важность нерешенной проблемы доказать равенство или неравенство между P и NP, и повышает эффективность пыток как метода достижения заданной цели.