Законодательство NP-полное?

64

Я хотел бы знать, была ли какая-либо работа, связывающая правовой кодекс со сложностью. В частности, предположим, что у нас есть проблема решения «Учитывая этот закон и этот конкретный набор обстоятельств, виновен ли ответчик?» К какому классу сложности он относится?

Есть результаты, которые доказали, что карточная игра Magic: the Gathering является NP-и Turing-complete, поэтому разве не должно быть похожих результатов для юридического кода?

Бьорн Линдквист
источник
18
Ваше заявление о MtG не может быть правильным, так как есть решаемые проблемы, которых нет в NP . Так что я предполагаю, что вы имеете в виду, что какая-то часть игры является NP -полной, а другая - Turing-complete.
Дэвид Ричерби
8
Мой профессор опубликовал несколько работ по формальному анализу законодательства, таких как этот , этот и этот . Я не думаю, что это именно то, что вы просите, но на тот случай, если вы сочтете это уместным
Jdehesa
1
Класс сложности под названием «юристы способны на бесконечную сложность». ;) Если вы заинтересованы в формальном анализе какой-то произвольно определенной абстрактной структуры, предназначенной для аппроксимации кодов законов некоторыми конкретными способами, этот формальный анализ может оказаться возможным. Однако важно признать, что это не будет иметь никакого отношения к реальным судебным делам и реальной системе правосудия, даже в идеализированном мире. Намерения имеют значение, и большая часть судебных дел устанавливает обстоятельства , в первую очередь.
Wildcard
9
Это полностью зависит от того, оплачивается ли время вычислений.
Мэтт Тиммерманс
1
Кратким справочником по сложности MtG может быть Chatterjee & Ibsen-Jensen, 1998 . Конечно, есть другие документы на эту тему.
Дмитрий Чубаров

Ответы:

33

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

Давайте возьмем, например, раздел 187 (а) Уголовного кодекса Калифорнии («Убийство в первой степени»).

(а) Убийство - это незаконное убийство человека или плода со злым умыслом.

(b) Этот раздел не применяется к любому лицу, совершившему действие, которое приводит к смерти плода, если применимо любое из следующего:

(1) Этот акт соответствовал Закону о терапевтическом аборте, статья 2 (начиная с раздела 123400) главы 2 части 2 раздела 106 Кодекса по охране здоровья и безопасности.

(2) Это деяние было совершено обладателем сертификата врача и хирурга, как это определено в Кодексе предпринимательской деятельности и профессий, в случае, если, по медицинским показаниям, результатом родов будет смерть матери плода или где ее смерть от родов, хотя и не определена с медицинской точки зрения, была бы в значительной степени достоверной или более вероятной, чем нет.

(3) Акт был запрошен, поддержан, поддержан или одобрен матерью зародыша.

(c) Подраздел (b) не должен толковаться как запрещающий судебное преследование любого лица в соответствии с любым другим положением закона.

Это может быть выражено как простой набор логической логики.

IF !victim.isAlive
   AND victim.species == HUMAN
   AND defendant.hasKilled( victim )
   AND defendant.hadMaliceForethought
   AND !(     victim.age < 0 
          AND wasTherapeuticAbortion 
          AND defendant.profession == DOCTOR 
          AND ( victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5 )
          AND victim.mom.wantedAbortion )
THEN defendant.moveTo(PRISON)

Теперь, конечно, здесь есть много чего, например, «что такое злая предвидение», «что такое терапевтический аборт» и «как вы определяете вероятность выживания беременности». Но они также могут быть выражены как похожие логические деревья решений.

С точки зрения разработки программного обеспечения, правовая система может рассматриваться как форма механизма бизнес-правил, а закон является его набором правил.

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

Однако иногда законы включают язык, который вообще не поддается определению и требует внешнего оракула. Например, когда упоминаются такие понятия, как «разумное сомнение». Что такое "разумный"? Это решать суду.

Philipp
источник
4
Это хорошо. Для вашего примера я думаю, что некоторые из связанных с абортом AND должны быть OR - «любой из следующих». Также я не вижу упоминания о шансе выживания жертв
Иосия
1
+1, но, как намекает Иосия, victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5не является правильным толкованием закона; закон говорит victim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5, что можно упростить до справедливости victim.mom.survivalChance < 0.5.
Руах
4
Просто придираться: если какой - либо из следующих действий не приводит к x AND y AND zа x OR y OR z.
Томаш Зато
3
Если бы это было так просто, почему у нас есть судьи? Почему нас так волнует, кто они? Почему у нас юриспруденция? Почему так много спорных судебных дел? Понятно, что закон не так прост, как вы его представляете. Разумное сомнение является хорошим примером проблемной части (которая встречается довольно часто), другой может быть создание повествования из произвольного набора доказательств или даже принятие решения о сроке тюремного заключения.
11684
1
Это еще хуже. Не только юридический язык может включать произвольный язык. Он также не может включать неявные предположения. Так что теоретически это может быть бесконечно сложным. Кроме того, человеческий язык настолько сложен и неявен, что вы можете задать определение любого слова в любом предложении, побуждая кого-то это объяснить. Это также может продолжаться вечно. Другими словами, общение и все, что выражается в общении, даже не гарантируется, чтобы иметь смысл, быть четко определенным или когда-либо прекращаться при выполнении.
Надеюсь, что вы
95

Это неразрешимо, потому что книга закона может включать произвольную логику. Глупым примером закона о цензуре может быть «незаконно публиковать любую компьютерную программу, которая не останавливается».

Причина, по которой результаты для MTG существуют и являются интересными, заключается в том, что у нее есть один фиксированный набор (в основном) однозначных правил, в отличие от закона, который постоянно меняется, ужасно локализован и бесконечно неоднозначен.

orlp
источник
1
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
DW
Уведомление модератора (снова): комментарии не для расширенного обсуждения. Если вы хотите обсудить этот ответ, используйте чат . Любой комментарий, опубликованный после существования чата, может быть удален.
Жиль "ТАК - перестань быть злым"
3
Это может быть даже хуже, чем неразрешимый, то есть не правильно определен или противоречив. Вспомните законопроект Индианы Пи
Хендрик,
10

Это очень интересный вопрос.

Закон - это что-то среднее между обычным языком с его произвольными, постоянно меняющимися и часто мягкими правилами и языком программирования с его очень конкретными, определенными правилами.

Легалезный фактически определяет свои термины, и поэтому многие слова (но не все!), Используемые в законе, действительно имеют точное значение.

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

Хороший пример - самооборона. В большинстве правовых систем вы можете на законных основаниях причинить боль другому человеку, если вы действуете в целях самообороны. Тем не менее, формулировка явно контекстно-зависимая. Например, британский уголовный закон пишет:

Человек может использовать такую ​​силу, которая является разумной в данных обстоятельствах для предотвращения преступления [...]

Прецедентное право определяет, что является «разумным» в конкретных случаях , но в книгах нет общего определения. Существует также прецедентное право, разъясняющее, что именно означает «предотвращение преступления». Поскольку по определению преступление еще не совершено, тем более суд, решивший, что иск фактически является преступлением, в данном конкретном случае достаточно разумных убеждений , но это на самом деле не прописано в законе!

Чтобы создать лицо, принимающее цифровые решения о законе, вы должны будете кормить его не только самим законом, но и всей прецедентной практикой, большим пониманием естественного языка и множеством правил о том, как применять все эти знания, потому что иногда прецедентное право является твердым, иногда вы можете согнуть его (особенно если оно старое, поскольку интерпретации меняются со временем)

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

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

Эти факторы окружающей среды делают оценку сложности почти невозможной, потому что мы не можем перечислить их в конечном списке, если не будем использовать все-кванторы (например, «каждый вид ...» или «все ...»)

Том
источник
8

NP-полнота, как и в других классах сложности, связана с задачами, требующими ввода различного размера, размер которого мы обозначим через n . В частности:

  • Проблема в NP, если возможно определить, является ли любое предложенное решение на самом деле решением с полиномом времени выполнения по n .

  • Задача является NP-полной, если она является NP, и, более того, каждая NP-задача может быть сведена к ней с помощью процесса сокращения с полиномом времени выполнения по n .

В предложенной вами проблеме, а именно

Является ли обвиняемый виновным с учетом этого сборника законов и данного набора обстоятельств?

Я не уверен, что п должен быть. Похоже, что здесь вводятся «набор обстоятельств» и имя обвиняемого. Только первый может быть разной длины, но что же мы подразумеваем под «набором обстоятельств»? Должны ли мы просто указать произвольное количество произвольных фактов, таких как «обвиняемый владеет фиолетовыми носками» и «сегодня у судьи был бутерброд на обед» или как? Более того, есть ли ограничения на эти обстоятельства, или мы можем питаться в таких «обстоятельствах», как «Севильский цирюльник бреет именно тех парикмахеров, которые не бреются сами»?

Я не думаю, что этот вопрос является корректным, и при этом я не вижу очевидного способа сделать его корректным.

Дэниел МакЛори
источник
Перед началом судебного разбирательства система правосудия проводит предварительное расследование (не уверен, что это правильное английское слово), в котором собраны все соответствующие обстоятельства. Размер документов, собирающих эти обстоятельства, зависит от сложности преступления - для простых дел - всего несколько десятков страниц, а для сложных (например, антимонопольного законодательства Microsoft) - десятки тысяч страниц и более.
Бьорн Линдквист
5

Я думаю, что в отличных ответах до сих пор не хватает того, что теория вычислений предполагает известные, определенные входные данные, в то время как законодательство действует в области, где факты обычно неопределенны и нечетки. Уголовное право, например, касается «намерения» или «состояния ума» подсудимого, которое никогда не может быть известно с уверенностью. Суды по бракоразводным процессам должны решить, был ли брак "безвозвратно разрушен". Там никогда не может быть алгоритм для решения этого вопроса.

Майкл Кей
источник
0

Хотя в некоторых ответах говорится, что это неразрешимо, я полагаю, что это не то, для чего нужны законы, поскольку они не подлежат исполнению.

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

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

Там будет больше проблем, если криптография участвует. Теоретически они могли бы обратить вспять алгоритм надежного шифрования, если бы они могли вычислять очень долго, но они могут подорвать доверие к алгоритму подписи, чтобы сделать его неиспользуемым в качестве доказательства одновременно.

user23013
источник
0

Члены жюри в конечном итоге выносят вердикты на основании применимого законодательства, вынесенного судьями присяжным, и фактов, определенных жюри с использованием факторов в инструкциях жюри. Особенно доверие к свидетелям ... кому верить. Не сводится к алгоритму.

Том Уитакер-младший
источник
Это, кажется, довольно философский ответ, в отличие от компьютерного. Это не делает это неправильно, но, вероятно, не полезно для вопроса, заданного на этом сайте.
Рафаэль
Зависит от того, рассматривает ли CS основную правдивость приложения и возможно ли это или нет. На данный момент любое обсуждение без включения точек соприкосновения AI кажется неуместным. Но это из более чем 35-летнего суда, а не гуру.
Том Уитакер-младший
1
Этот ответ является хорошим напоминанием о том, насколько далека теория вычислимости или разрешимости CS от юридической практики.
Apass.Jack
@ TomWhitakerJr С моей точки зрения, с целью сохранения охвата этого сайта, хотя применение методов CS должно быть связано с этическими / философскими соображениями, изучение этих методов не является. Я полностью осознаю, что там лежат долгие дискуссии, но я просто не понимаю, как мы можем сделать этот сайт одинаково хорошо работающим для технических и этических / философских вопросов. Таким образом , в то время как я полностью согласен , что дискуссии , такие как , как AI следует использовать , должны проходить где - то, я не думаю этом сайте место для этого.
Рафаэль