математическо-политическое
Aug. 29th, 2009 11:57 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВажность вопроса P?=NP напрямую связана с эффективностью пыток.
Вопрос P?=NP важен потому, что так много сложных задач - не только в информатике, но и в других разных науках - которые мы не умеем эффективно решать, относятся к классу NP. Это значит, что если есть вариант решения, то проверить, правильное это решение или нет, можно очень быстро; но найти правильное решение - очень тяжело и требует слишком много времени и сил.
Предположим, на острове закопано сокровище, а у вас есть лопата, и вы хотите его найти. Если вам кто-то даст карту, на которой отмечено крестиком нужное место, то проверить этот "вариант решения" довольно просто - пойти туда и попробовать копать. Но если карты у вас нет, то найти нужное решение тяжело - неясно, что можно сделать, кроме как перекопать весь остров (если у вас нет дополнительной информации).
Если окажется, что P=NP (во что мало кто верит), это будет значить, в предложенной аналогии, что каким-то странным и непонятным образом можно будет найти клад, не копая всюду, всего за несколько попыток, пользуясь только тем, что одну отдельную попытку можно сделать быстро. Казалось бы, это очевидный бред, но, наверное, не очень очевидный, раз доказать обратное - что P не равно NP - тоже никому не удается уже сорок лет.
О пытках часто говорят, что они неэффективны, потому что подвергающиеся пыткам люди говорят то, что хотят услышать пытчики, а вовсе необязательно правду. Что если они не знают правду, то будут говорить наобум, чтобы прекратили пытки. Итп. В какой-то степени это верно, но в какой точности, я не знаю. Подозреваю, что многие из таких утверждений основаны на идеологической убежденности, а не на фактах или опыте. Так как я в любом случае считаю, что пытки недопустимы и должны быть запрещены, мне не очень важно разбираться в этом вопросе.
Но если все же задуматься об этом, то видим, что даже если все, что говорят о ложных и неточных ответах, о "говорят то, что хотят услышать пытчики" - даже если все это верно, это необязательно показывает неэффективность пыток. Суть в том, что вопросы, ответы на которые ищут с помощью пыток, часто оказываются NP-задачами: предполагаемый ответ легко проверить. Предположим, мы поймали 20 пиратов, которые когда-то имели отношение к этому острову, и, возможно, даже к спрятанному сокровищу (мы не знаем точно; у нас есть всякие косвенные свидетельства, а сами пираты все отрицают, естественно). Мы их всех пытаем с целью узнать, где клад. Часть пиратов ничего не скажет под пытками. Кто-то, может, умрет от них. Кто-то ничего не знает, но будет говорить наугад, только бы перестали пытать. Кто-то, может, знает, но скажет неверное место. Но все это не очень важно, потому что мы так легко может проверить любой вариант - просто послать пару человек с лопатой в это место на пару часов. Если мы получили десять вариантов, и только один из них на самом деле верный - ничего страшного, перепробуем все десять и найдем клад. А если ни один не оказался верным - что ж, будем пытать дальше или еще пиратов искать. Если действительно есть пираты, которые знают, где клад, и у нас есть шанс их поймать, то очень может быть, что в итоге мы обнаружим сокровище, и значит, пытки в этом случае окажутся эффективным методом.
Но если немного изменить условие, так, чтобы задача уже не была в NP - то есть, проверка варианта была довольно сложным занятием - и эффективность пыток резко падает. Если весь остров зарос джунглями, и чтобы пробиться к каждому месту проверки, нужно три месяца и двадцать человек, из которых пятеро умрут от укусов змей и малярии, то наличие десяти разных возможностей уже не кажется многообещающим. Если мы пытаем террориста, чтобы узнать, где спрятана бомба, но у нас в любом случае есть время только на одну попытку ее найти и нейтрализовать - то внезапно вопрос о том, не говорит ли он что-то наугад, лишь бы его перестали пытать, становится весьма важным.
Очень многие практические проблемы в окружающем мире устроены подобно NP-задачам. Это обстоятельство одновременно демонстрирует важность нерешенной проблемы доказать равенство или неравенство между P и NP, и повышает эффективность пыток как метода достижения заданной цели.
Вопрос P?=NP важен потому, что так много сложных задач - не только в информатике, но и в других разных науках - которые мы не умеем эффективно решать, относятся к классу NP. Это значит, что если есть вариант решения, то проверить, правильное это решение или нет, можно очень быстро; но найти правильное решение - очень тяжело и требует слишком много времени и сил.
Предположим, на острове закопано сокровище, а у вас есть лопата, и вы хотите его найти. Если вам кто-то даст карту, на которой отмечено крестиком нужное место, то проверить этот "вариант решения" довольно просто - пойти туда и попробовать копать. Но если карты у вас нет, то найти нужное решение тяжело - неясно, что можно сделать, кроме как перекопать весь остров (если у вас нет дополнительной информации).
Если окажется, что P=NP (во что мало кто верит), это будет значить, в предложенной аналогии, что каким-то странным и непонятным образом можно будет найти клад, не копая всюду, всего за несколько попыток, пользуясь только тем, что одну отдельную попытку можно сделать быстро. Казалось бы, это очевидный бред, но, наверное, не очень очевидный, раз доказать обратное - что P не равно NP - тоже никому не удается уже сорок лет.
О пытках часто говорят, что они неэффективны, потому что подвергающиеся пыткам люди говорят то, что хотят услышать пытчики, а вовсе необязательно правду. Что если они не знают правду, то будут говорить наобум, чтобы прекратили пытки. Итп. В какой-то степени это верно, но в какой точности, я не знаю. Подозреваю, что многие из таких утверждений основаны на идеологической убежденности, а не на фактах или опыте. Так как я в любом случае считаю, что пытки недопустимы и должны быть запрещены, мне не очень важно разбираться в этом вопросе.
Но если все же задуматься об этом, то видим, что даже если все, что говорят о ложных и неточных ответах, о "говорят то, что хотят услышать пытчики" - даже если все это верно, это необязательно показывает неэффективность пыток. Суть в том, что вопросы, ответы на которые ищут с помощью пыток, часто оказываются NP-задачами: предполагаемый ответ легко проверить. Предположим, мы поймали 20 пиратов, которые когда-то имели отношение к этому острову, и, возможно, даже к спрятанному сокровищу (мы не знаем точно; у нас есть всякие косвенные свидетельства, а сами пираты все отрицают, естественно). Мы их всех пытаем с целью узнать, где клад. Часть пиратов ничего не скажет под пытками. Кто-то, может, умрет от них. Кто-то ничего не знает, но будет говорить наугад, только бы перестали пытать. Кто-то, может, знает, но скажет неверное место. Но все это не очень важно, потому что мы так легко может проверить любой вариант - просто послать пару человек с лопатой в это место на пару часов. Если мы получили десять вариантов, и только один из них на самом деле верный - ничего страшного, перепробуем все десять и найдем клад. А если ни один не оказался верным - что ж, будем пытать дальше или еще пиратов искать. Если действительно есть пираты, которые знают, где клад, и у нас есть шанс их поймать, то очень может быть, что в итоге мы обнаружим сокровище, и значит, пытки в этом случае окажутся эффективным методом.
Но если немного изменить условие, так, чтобы задача уже не была в NP - то есть, проверка варианта была довольно сложным занятием - и эффективность пыток резко падает. Если весь остров зарос джунглями, и чтобы пробиться к каждому месту проверки, нужно три месяца и двадцать человек, из которых пятеро умрут от укусов змей и малярии, то наличие десяти разных возможностей уже не кажется многообещающим. Если мы пытаем террориста, чтобы узнать, где спрятана бомба, но у нас в любом случае есть время только на одну попытку ее найти и нейтрализовать - то внезапно вопрос о том, не говорит ли он что-то наугад, лишь бы его перестали пытать, становится весьма важным.
Очень многие практические проблемы в окружающем мире устроены подобно NP-задачам. Это обстоятельство одновременно демонстрирует важность нерешенной проблемы доказать равенство или неравенство между P и NP, и повышает эффективность пыток как метода достижения заданной цели.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-08-29 09:31 pm (UTC)no subject
Date: 2009-08-29 09:39 pm (UTC)no subject
Date: 2009-08-29 09:40 pm (UTC)no subject
Date: 2009-08-29 09:40 pm (UTC)no subject
Date: 2009-08-29 09:48 pm (UTC)у пыток, на самом деле, кроме обычного садизма, может быть три разных цели:
- чтобы заставить человека себя оговорить
- чтобы заставить не высовываться в будущем
- чтобы узнать правду
первые два случая, на самом деле, куда более распространены, потому что как раз в случае NP-задач можно просто влить человеку что-нибудь типа "сыворотки правды" (да или просто напоить его хорошенько!), развязав ему язык.
но если и пытают для этих целей, то рассчитывают не на то, что человек скажет во время пытки, а на то, что он будет говорить позже - эмоционально подавленный, с хронической болью итд - в положении, когда ему просто будет тяжелее врать.
но это все отвратительно - и в любом случае завязано на удовлетворении садистских потребностей пытающего - что даже и не знаю, стоит ли на эти темы теоретизировать [edit: я думаю, первый комментатор примерно это имел в виду]
no subject
Date: 2009-08-29 09:48 pm (UTC)no subject
Date: 2009-08-29 09:52 pm (UTC)no subject
Date: 2009-08-29 09:53 pm (UTC)no subject
Date: 2009-08-29 09:59 pm (UTC)no subject
Date: 2009-08-29 10:00 pm (UTC)no subject
Date: 2009-08-29 10:02 pm (UTC)сравните это с отбитыми почками, waterboarding etc
no subject
Date: 2009-08-29 10:03 pm (UTC)no subject
Date: 2009-08-29 10:06 pm (UTC)no subject
Date: 2009-08-29 10:11 pm (UTC)no subject
Date: 2009-08-29 10:14 pm (UTC)no subject
Date: 2009-08-29 10:45 pm (UTC)no subject
Date: 2009-08-29 10:51 pm (UTC)здравый смысл и мораль
Date: 2009-08-29 10:52 pm (UTC)> пытки недопустимы и должны быть запрещены
Если при этом подразумевать "в обычных ситуациях", то с этим нельзя не согласиться. Разного рода "моральные принципы" -- это своего рода "статистические закономерности". Они хорошо работают в случаях "общего положения", но к ситуациям "экстремальным" они, вообще говоря, неприменимы.
Ну вот банальный пример: если поймали террориста, который заложил несколько бомб, обезвреживание которых требует получения некой срочной информации, то как Вы считаете -- дало ли бы общество своё "добро" на применение пыток в этой заведомо "экстремальной" ситуации?
Поскольку для меня здравый смысл важнее "морали" (которую я считаю "вторичной"), то я бы не думая одобрил бы такое решение. Всякий человек, отрицая пытки, боится в том числе и того, что где-то могут пытать и его самого. Но какой смысл этого бояться тому, кто ни при каких условиях не стал бы закладывать бомбы для массовых террористических актов?
То есть я считаю, что вполне возможно "цивилизованное" и "гуманное" общество, которое вполне допускает возможность применения пыток в особо оговорённых законом ситуациях. И мне хотелось бы понять, какими соображениями руководствуются те, кто испытывает "мистический страх" и говорит "нет, никогда".
И ещё одно замечание насчёт "запрета": дело в том, что не все запреты соблюдаются. Это не значит, что запретов быть не должно, но это значит как минимум то, что сам по себе запрет всё равно не даёт никаких гарантий. В том смысле, что если человек способен на применение пыток по отношению к кому-либо, то он не остановится перед какими-то запретами.
no subject
Date: 2009-08-29 10:55 pm (UTC)По поводу Р НР, я не программист, но вроде есть задача про посыльного который должен проложить оптимальный маршрут, чтобы потратить меньше всего денег - если определение НР полной задачи что "если есть вариант решения, то проверить, правильное это решение или нет, можно очень быстро" - то как проверяется что именно данное решение является оптимальным, если мы не знаем верен ли ответ? На ведь для этого надо знать все возможные пути, а после их нахождения очень просто найти именно тот правильный.
no subject
Date: 2009-08-29 10:56 pm (UTC)no subject
Date: 2009-08-29 10:57 pm (UTC)а насчет подвижной границы, для тех кто ее хочет изучать - она похожа на подвижную границу при определении physical abuse, sexual abuse, emotional abuse, verbal abuse. мне опять же всегда казалось что границы должны быть четкие - первые два, если доказаны, да, остальные два - нет. одно дело бабу называть каждый день дурой и совсем другое прижигать сигаретами.... одно дело держать подозреваемого в терроризме без сна и совсем дргое ему коран не давать. я бы вот не дала..
no subject
Date: 2009-08-29 11:10 pm (UTC)Если, например, клад точечный, а раскапываем мы некоторую площадь, то с подсказкой мы выкопаем за одну попытку, а без максимум за целая часть от [ (площадь острова)/(площадь раскопок)]. Это как равенство классов? Типа конст = конст. Или нет?
no subject
Date: 2009-08-29 11:14 pm (UTC)Re: здравый смысл и мораль
Date: 2009-08-29 11:23 pm (UTC)no subject
Date: 2009-08-29 11:31 pm (UTC)