¿Está completa la legislación NP?

64

Me gustaría saber si ha habido algún trabajo que relacione el código legal con la complejidad. En particular, supongamos que tenemos el problema de decisión "Dado este libro de leyes y este conjunto particular de circunstancias, ¿es el acusado culpable?" ¿A qué clase de complejidad pertenece?

Hay resultados que han demostrado que el juego de cartas Magic: the Gathering es NP y Turing completo, ¿no deberían existir resultados similares para el código legal?

Björn Lindqvist
fuente
18
Su afirmación sobre MtG no puede ser correcta, ya que hay problemas decidibles que no están en NP . Así que supongo que quieres decir que una parte del juego es NP -completa, y otra parte es Turing-complete.
David Richerby
8
Un profesor mío publicó algunos trabajos sobre análisis formal de legislación, como esto , esto y esto . No creo que sea exactamente lo que está preguntando, pero en caso de que lo encuentre relevante.
jdehesa
1
La clase de complejidad llamada "los abogados son capaces de una complejidad infinita". ;) Si está interesado en el análisis formal de alguna estructura abstracta definida arbitrariamente diseñada para aproximar los códigos legales de alguna manera específica, ese análisis formal puede ser posible. Sin embargo, es importante reconocer que no se relacionará de manera significativa con los casos judiciales reales y el sistema de justicia real , incluso en un mundo idealizado. Asuntos intención, y una gran parte de los casos judiciales es establecer cuáles son las circunstancias son , en primer lugar.
Comodín el
99
Depende completamente de si el tiempo de cálculo es facturable o no.
Matt Timmermans el
1
Una referencia rápida sobre la complejidad de MtG podría ser Chatterjee & Ibsen-Jensen, 1998 . Seguramente hay otros documentos sobre el tema.
Dmitri Chubarov

Respuestas:

33

Las leyes pueden incluir lenguaje arbitrario, y el lenguaje arbitrario puede expresar la lógica NP-completa. Entonces, en teoría, sería posible crear un NP completo o incluso una ley indecidible. Sin embargo, en la práctica, la gran mayoría de las leyes penales son simples árboles de decisión.

Tomemos, por ejemplo, la sección 187 (a) del código penal de California ("Asesinato en primer grado").

(a) El asesinato es el asesinato ilegal de un ser humano, o un feto, con malicia premeditada.

(b) Esta sección no se aplicará a ninguna persona que cometa un acto que resulte en la muerte de un feto si se aplica alguno de los siguientes:

(1) La ley cumplió con la Ley de Aborto Terapéutico, Artículo 2 (que comienza con la Sección 123400) del Capítulo 2 de la Parte 2 de la División 106 del Código de Salud y Seguridad.

(2) El acto fue cometido por un titular de un certificado médico y de cirujano, como se define en el Código de Negocios y Profesiones, en un caso donde, con certeza médica, el resultado del parto sería la muerte de la madre del feto o donde su muerte por parto, aunque no sea médicamente segura, sería sustancialmente cierta o más probable que no.

(3) El acto fue solicitado, ayudado, instigado o consentido por la madre del feto.

(c) La subdivisión (b) no se interpretará en el sentido de prohibir el enjuiciamiento de ninguna persona en virtud de cualquier otra disposición de la ley.

Esto se puede expresar como un conjunto simple de lógica booleana.

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)

Ahora, por supuesto, hay muchas cosas que trivializo aquí, como "qué es la previsión maliciosa", "qué es un aborto terapéutico" y "cómo se determina la probabilidad de supervivencia de un embarazo". Pero estos también se pueden expresar como árboles de decisión booleanos similares.

Desde el punto de vista de la ingeniería de software, el sistema legal puede ser visto como una forma de Motor de Reglas de Negocio, siendo la ley su conjunto de reglas.

Eso significa que la mayoría de las leyes tienen una complejidad computacional de c. Si también tiene en cuenta el proceso de examen de evidencia que se requiere para determinar los valores de todas estas variables booleanas, entonces la complejidad se convierte en ndónde nestá la cantidad de evidencia que debe evaluarse.

Sin embargo, a veces las leyes incluyen un lenguaje que no es decidible en absoluto y requiere un oráculo externo. Por ejemplo, cuando menciona conceptos como "duda razonable". ¿Qué es "razonable"? Eso lo decidirá un tribunal.

Philipp
fuente
44
Esto es bueno. Para su ejemplo, creo que algunos de los AND relacionados con el aborto deberían ser OR: "cualquiera de los siguientes". Tampoco veo la posibilidad de supervivencia de la víctima mencionada aquí.
Josías el
1
+1, pero como Josías alude, victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5no es una interpretación correcta de la ley; dice la ley victim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5, que se puede simplificar a justo victim.mom.survivalChance < 0.5.
ruakh
44
Solo un poco: si alguno de los siguientes casos no se traduce en x AND y AND zpero x OR y OR z.
Tomáš Zato
3
Si fuera así de simple, ¿por qué tenemos jueces? ¿Por qué nos importa tanto quiénes son? ¿Por qué tenemos jurisprudencia? ¿Por qué hay tantos casos judiciales controvertidos? Claramente, la ley no es tan simple como parece ser. La duda razonable es un buen ejemplo de una parte problemática (que ocurre con bastante frecuencia), otra sería construir una narrativa a partir de un conjunto arbitrario de evidencia o incluso decidir la duración de una sentencia de prisión.
11684
1
Es aun peor. El lenguaje legal no solo puede incluir lenguaje arbitrario. Tampoco puede incluir supuestos implícitos. Por lo tanto, en teoría puede ser infinitamente complejo. Además, el lenguaje humano es tan complejo e implícito, que puede pedir la definición de cualquier palabra en cualquier oración, lo que lleva a alguien a explicarlo. Esto también puede continuar para siempre. En otras palabras, la comunicación y todo lo que se expresa en la comunicación, ni siquiera está garantizado para tener sentido, estar bien definido o terminar, cuando se ejecuta.
HopefulHelpful
95

Es indecidible porque un libro de leyes puede incluir lógica arbitraria. Un ejemplo tonto de ley de censura sería "es ilegal publicitar cualquier programa de computadora que no se detenga".

La razón por la que existen los resultados para MTG y son interesantes es porque tiene un conjunto fijo único de reglas (en su mayoría) inequívocas, a diferencia de la ley que siempre está cambiando, terriblemente localizada y sin fin ambigua.

orlp
fuente
1
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
Aviso del moderador (nuevamente): los comentarios no son para una discusión prolongada. Si desea discutir esta respuesta, use la sala de chat . Cualquier comentario publicado una vez que exista una sala de chat puede ser eliminado sumariamente.
Gilles 'SO- deja de ser malvado'
3
Puede ser incluso peor que indecidible, lo que significa que no está adecuadamente definido o es contradictorio. Recuerde el proyecto de ley de Indiana Pi
Hendrik
10

Esta es una pregunta muy interesante.

La ley se encuentra en algún lugar entre el lenguaje cotidiano con sus reglas arbitrarias, en constante cambio y a menudo suaves, y el lenguaje de programación con sus reglas definidas y muy específicas.

Legalés en realidad define sus términos y, por lo tanto, muchas palabras (¡pero no todas!) Utilizadas en la ley realmente tienen significados precisos.

Sin embargo, la interpretación es donde su enfoque de presentar un caso a un sistema lógico y obtener un resultado fallará. La ley es una definición genérica que debe adaptarse al caso específico en cuestión. A menudo, este es un proceso trivial y directo, pero no hay garantía de que lo sea y no hay una forma no trivial de definir el límite.

Un buen ejemplo es la defensa propia. En la mayoría de los sistemas legales, puede lastimar legalmente a otra persona siempre que actúe en defensa propia. Sin embargo, la redacción es explícitamente sensible al contexto. Por ejemplo, el derecho penal británico escribe:

Una persona puede usar la fuerza que sea razonable en las circunstancias en la prevención del delito [...]

La jurisprudencia define lo que es "razonable" en casos específicos , pero no hay una definición general en los libros. También hay jurisprudencia que aclara qué significa exactamente "prevención del delito". Dado que, por definición, aún no se ha producido un delito, mucho menos que un tribunal haya decidido que la acción fue, de hecho, un delito, una creencia razonable es suficiente en este caso particular, ¡pero eso no está escrito en la ley!

Para crear un tomador de decisiones digital sobre la ley, tendría que alimentarlo no solo la ley en sí, sino también toda la jurisprudencia, mucha comprensión del lenguaje natural y muchas reglas sobre cómo aplicar todo ese conocimiento, porque a veces la jurisprudencia es sólida, a veces se puede doblar (especialmente si es antigua, ya que las interpretaciones cambian con el tiempo).

Y finalmente, la ley cambia y se adapta, no solo en el libro, sino también en sus interpretaciones. Hay muchos ejemplos famosos de tribunales superiores que anulan su propia decisión de 20 años. Muy a menudo, tales desafíos a la jurisprudencia anterior suceden exactamente porque un juez decidió ir en contra de esas leyes establecidas y preferiría correr el riesgo de ser anulado en el tribunal superior que pasar una decisión que no respalda. Me pregunto cómo modelarías esta habilidad en un sistema NP-complete.

Calcular la complejidad de un sistema requiere que comprendamos las entradas y salidas. La ley, sin embargo, es un sistema abierto. Literalmente, cualquier cosa en su entorno puede influir en él, especialmente los cambios en la sociedad y la cultura. La mayoría de los países tienen leyes en los libros que rara vez se aplican porque la sociedad ha cambiado, pero el proceso de elaboración de leyes va a la zaga. Las leyes contra la homosexualidad son un ejemplo actual. O la sentencia de muerte, que en la mayoría de los países no se había aplicado durante años o décadas antes de que fuera eliminada de los libros de leyes. Y no porque no haya casos en los que podría haberse aplicado, sino simplemente porque los jueces no lo aplicaron a pesar de tener la opción.

Estos factores ambientales hacen que una estimación de complejidad sea casi imposible, porque no podemos enumerarlos en una lista finita a menos que usemos todos los cuantificadores (por ejemplo, "todo tipo de ..." o "todo el ...")

Tom
fuente
8

La completitud de NP, como con otras clases de complejidad, tiene que ver con problemas que toman una entrada de tamaño variable, cuyo tamaño denotamos por n . En particular:

  • Un problema es NP si es posible determinar si alguna solución propuesta es realmente una solución con polinomio de tiempo de ejecución en n .

  • Un problema es NP completo si es NP y, además, todos los problemas de NP pueden reducirse mediante un proceso de reducción con polinomio de tiempo de ejecución en n .

En el problema que propones, a saber

Dado este libro de leyes y este conjunto particular de circunstancias, ¿es el acusado culpable?

No estoy seguro de lo que n debe ser. Parece que las entradas aquí son el "conjunto de circunstancias" y el nombre del acusado. Solo el primero podría tener una longitud variable, pero entonces, ¿qué queremos decir con "conjunto de circunstancias"? ¿Acabamos de alimentar un número arbitrario de hechos arbitrarios como "el acusado tiene medias moradas" y "el juez comió un sándwich hoy" o qué? Además, ¿existen limitaciones en estas circunstancias, o podemos alimentarnos en una "circunstancia" como "el barbero de Sevilla afeita precisamente a los barberos que no se afeitan"?

No creo que esta pregunta esté bien planteada, ni veo ninguna forma obvia de hacerla bien.

Daniel McLaury
fuente
Antes del juicio, el sistema de justicia lleva a cabo una investigación preliminar (no estoy seguro si esa es la palabra correcta en inglés) en la que se recopilan todas las circunstancias relevantes. El tamaño de los documentos que recopilan estas circunstancias depende de la complejidad del delito: para casos simples de solo unas pocas docenas de páginas y para casos complejos (por ejemplo, antimonopolio de Microsoft), decenas de miles de páginas o más.
Björn Lindqvist
5

Creo que lo que falta en las excelentes respuestas hasta ahora es que la teoría de la computación asume datos de entrada conocidos, ciertos, mientras que la legislación opera en un campo donde los hechos son generalmente inciertos y confusos. El derecho penal, por ejemplo, se refiere a la "intención" o "estado mental" de un acusado, que nunca se puede conocer con certeza. Los tribunales de divorcio tienen que decidir si un matrimonio se ha "roto irremediablemente". Nunca puede haber un algoritmo para decidir esa pregunta.

Michael Kay
fuente
0

Si bien algunas respuestas dicen que es indecidible, supongo que no es para lo que son las leyes, ya que no son exigibles.

Si está restringido de alguna manera que lo hace siempre decidible, probablemente no tenga mucho sentido hablar sobre la complejidad real. Esto se debe a que las entradas de las leyes como funciones generalmente no son definiciones de eventos en la ley, como en un juego de cartas, sino evidencias de que los eventos son legales o no.

Podría haber arbitrariamente muchas evidencias sobre un solo evento. Para un evento, no hay una longitud de entrada objetiva que permita definir la complejidad. Y para un conjunto dado de evidencias, aunque hay una longitud de entrada, las leyes generalmente no especifican que alguien debe tener una conclusión definitiva. Podrían, y generalmente prefieren tratar de recopilar más evidencias, incluso si la respuesta pudiera deducirse teóricamente de una manera difícil. Y un sospechoso podría admitir algo de una manera desconcertante para aumentar la complejidad artificialmente si uno tiene que trabajar sin evidencias.

Habría más problemas si la criptografía está involucrada. Teóricamente, podrían revertir un algoritmo de cifrado fuerte si pudieran calcular durante mucho tiempo, pero pueden romper la confianza de un algoritmo de firma para que no se pueda usar como evidencia al mismo tiempo.

usuario23013
fuente
0

Los miembros del jurado en última instancia emiten veredictos basados ​​en la ley aplicable dada por los jueces al jurado a seguir y los hechos según lo determine el jurado usando los factores en las instrucciones del jurado. Especialmente la credibilidad de los testigos ... a quién creer. No reducible a un algoritmo.

Tom Whitaker Jr
fuente
Esto parece ser una respuesta bastante filosófica, a diferencia de la informática. Eso no lo hace mal, pero probablemente no sea útil para una pregunta formulada en este sitio.
Raphael
Depende de si cs considera la verdad básica de una aplicación y si es factible o no. Por el momento, cualquier discusión sin inclusión de puntos de contacto de IA parece fuera de curso. Pero eso es de un atty de prueba de más de 35 años y no de un gurú de CS.
Tom Whitaker Jr
1
Esta respuesta es un buen recordatorio de cuán lejos está la computación de cs o la teoría de la capacidad de decisión de la práctica del derecho.
Apass.Jack
@TomWhitakerJr Mi perspectiva, con el propósito de mantener el alcance de este sitio, es que si bien la aplicación de las técnicas CS debe estar sujeta a consideraciones éticas / filosóficas, el estudio de esas técnicas no lo es. Soy plenamente consciente de que existen largas discusiones, pero simplemente no veo cómo podemos hacer que este sitio funcione igualmente bien para preguntas técnicas y éticas / filosóficas. Entonces, si bien estoy totalmente de acuerdo en que las discusiones, como la forma en que se debe usar la inteligencia artificial, deben realizarse en algún lugar, no creo que este sitio sea el lugar adecuado.
Raphael