Is legislation NP-complete?
up vote
53
down vote
favorite
I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?
There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?
complexity-theory np-complete decision-problem
|
show 1 more comment
up vote
53
down vote
favorite
I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?
There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?
complexity-theory np-complete decision-problem
14
Your claim about MtG can't be correct, since there are decidable problems that aren't in NP. So I guess you mean that some part of the game is NP-complete, and some other part is Turing-complete.
– David Richerby
Nov 27 at 13:32
7
A professor of mine published a few works on formal analysis of legislation, like this, this and this. I don't think it's quite what you're asking but just in case you find it relevant.
– jdehesa
Nov 27 at 15:08
The complexity class called "lawyers are capable of infinite complexity." ;) If you're interested in formal analysis of some arbitrarily defined abstract structure that's designed to approximate the law codes in some specific ways, that formal analysis may be possible. However, it's important to recognize that it won't relate in any meaningful way to actual court cases and the actual justice system, even in an idealized world. Intent matters, and a large part of court cases is establishing what the circumstances are in the first place.
– Wildcard
Nov 28 at 0:11
6
It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
Nov 29 at 2:46
1
A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject.
– Dmitri Chubarov
20 hours ago
|
show 1 more comment
up vote
53
down vote
favorite
up vote
53
down vote
favorite
I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?
There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?
complexity-theory np-complete decision-problem
I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?
There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?
complexity-theory np-complete decision-problem
complexity-theory np-complete decision-problem
edited Nov 28 at 17:01
Juho
15.1k54089
15.1k54089
asked Nov 27 at 11:46
Björn Lindqvist
4261410
4261410
14
Your claim about MtG can't be correct, since there are decidable problems that aren't in NP. So I guess you mean that some part of the game is NP-complete, and some other part is Turing-complete.
– David Richerby
Nov 27 at 13:32
7
A professor of mine published a few works on formal analysis of legislation, like this, this and this. I don't think it's quite what you're asking but just in case you find it relevant.
– jdehesa
Nov 27 at 15:08
The complexity class called "lawyers are capable of infinite complexity." ;) If you're interested in formal analysis of some arbitrarily defined abstract structure that's designed to approximate the law codes in some specific ways, that formal analysis may be possible. However, it's important to recognize that it won't relate in any meaningful way to actual court cases and the actual justice system, even in an idealized world. Intent matters, and a large part of court cases is establishing what the circumstances are in the first place.
– Wildcard
Nov 28 at 0:11
6
It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
Nov 29 at 2:46
1
A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject.
– Dmitri Chubarov
20 hours ago
|
show 1 more comment
14
Your claim about MtG can't be correct, since there are decidable problems that aren't in NP. So I guess you mean that some part of the game is NP-complete, and some other part is Turing-complete.
– David Richerby
Nov 27 at 13:32
7
A professor of mine published a few works on formal analysis of legislation, like this, this and this. I don't think it's quite what you're asking but just in case you find it relevant.
– jdehesa
Nov 27 at 15:08
The complexity class called "lawyers are capable of infinite complexity." ;) If you're interested in formal analysis of some arbitrarily defined abstract structure that's designed to approximate the law codes in some specific ways, that formal analysis may be possible. However, it's important to recognize that it won't relate in any meaningful way to actual court cases and the actual justice system, even in an idealized world. Intent matters, and a large part of court cases is establishing what the circumstances are in the first place.
– Wildcard
Nov 28 at 0:11
6
It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
Nov 29 at 2:46
1
A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject.
– Dmitri Chubarov
20 hours ago
14
14
Your claim about MtG can't be correct, since there are decidable problems that aren't in NP. So I guess you mean that some part of the game is NP-complete, and some other part is Turing-complete.
– David Richerby
Nov 27 at 13:32
Your claim about MtG can't be correct, since there are decidable problems that aren't in NP. So I guess you mean that some part of the game is NP-complete, and some other part is Turing-complete.
– David Richerby
Nov 27 at 13:32
7
7
A professor of mine published a few works on formal analysis of legislation, like this, this and this. I don't think it's quite what you're asking but just in case you find it relevant.
– jdehesa
Nov 27 at 15:08
A professor of mine published a few works on formal analysis of legislation, like this, this and this. I don't think it's quite what you're asking but just in case you find it relevant.
– jdehesa
Nov 27 at 15:08
The complexity class called "lawyers are capable of infinite complexity." ;) If you're interested in formal analysis of some arbitrarily defined abstract structure that's designed to approximate the law codes in some specific ways, that formal analysis may be possible. However, it's important to recognize that it won't relate in any meaningful way to actual court cases and the actual justice system, even in an idealized world. Intent matters, and a large part of court cases is establishing what the circumstances are in the first place.
– Wildcard
Nov 28 at 0:11
The complexity class called "lawyers are capable of infinite complexity." ;) If you're interested in formal analysis of some arbitrarily defined abstract structure that's designed to approximate the law codes in some specific ways, that formal analysis may be possible. However, it's important to recognize that it won't relate in any meaningful way to actual court cases and the actual justice system, even in an idealized world. Intent matters, and a large part of court cases is establishing what the circumstances are in the first place.
– Wildcard
Nov 28 at 0:11
6
6
It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
Nov 29 at 2:46
It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
Nov 29 at 2:46
1
1
A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject.
– Dmitri Chubarov
20 hours ago
A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject.
– Dmitri Chubarov
20 hours ago
|
show 1 more comment
7 Answers
7
active
oldest
votes
up vote
28
down vote
accepted
Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in practice the vast majority of criminal laws are simple decision trees.
Let's take, for example, section 187 (a) of the California penal code ("First Degree Murder").
(a) Murder is the unlawful killing of a human being, or a fetus, with
malice aforethought.
(b) This section shall not apply to any person
who commits an act that results in the death of a fetus if any of the
following apply:
(1) The act complied with the Therapeutic Abortion
Act, Article 2 (commencing with Section 123400) of Chapter 2 of Part 2
of Division 106 of the Health and Safety Code .
(2) The act was
committed by a holder of a physician's and surgeon's certificate, as
defined in the Business and Professions Code, in a case where, to a
medical certainty, the result of childbirth would be death of the
mother of the fetus or where her death from childbirth, although not
medically certain, would be substantially certain or more likely than
not.
(3) The act was solicited, aided, abetted, or consented to by the
mother of the fetus.
(c) Subdivision (b) shall not be construed to
prohibit the prosecution of any person under any other provision of
law.
This can be expressed as a simple set of boolean logic.
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)
Now there is of course a lot I trivialize here, like "what's malice forethought", "what is a therapeutic abortion" and "how do you determine the survival chance of a pregnancy". But these can also be expressed as similar boolean decision trees.
From a software engineering point of view, the legal system can be seen as a form of Business Rule Engine with the law being its ruleset.
That means that most laws have a computational complexity of c
. If you also take the process of evidence examination into account which is required to determine the values of all these boolean variables, then the complexity becomes n
where n
is the amount of evidence which needs to be evaluated.
However, sometimes laws include language which isn't decideable at all and requires an external oracle. For example, when it mentions concepts like "reasonable doubt". What is "reasonable"? That's for a court to decide.
New contributor
3
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
1
+1, but as Josiah alludes to,victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is sayingvictim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to justvictim.mom.survivalChance < 0.5
.
– ruakh
yesterday
3
Just a nitpick: if any of the following apply does not translate tox AND y AND z
butx OR y OR z
.
– Tomáš Zato
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
add a comment |
up vote
88
down vote
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".
The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.
1
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
add a comment |
up vote
7
down vote
This is a very interesting question.
Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined rules.
Legalese actually defines its terms and thus many words (but not all!) used in the law actually do have precise meanings.
However, interpretation is where your approach of presenting a case to a logical system and getting a result will fail. The law is a generic definition that needs to be adapted to the specific case in question. Often this is a trivial, straightforward process, but there is no guarantee that it is and no non-trivial way to define the boundary.
A good example is self-defense. In most law systems, you can lawfully hurt another person provided that you are acting in self-defense. However, the wording is explicitly context-sensitive. For example, the british criminal law writes:
A person may use such force as is reasonable in the circumstances in the prevention of crime [...]
Case law defines what is "reasonable" in specific cases, but no general definition is on the books. There is also case law clearing up what exactly "prevention of crime" means. Since by definition a crime has not yet occurred, much less a court having decided that the action was, in fact, a crime, reasonable belief is enough in this particular case, but that is not actually written in the law!
To create a digital decision maker about the law, you would have to feed it not just the law itself, but also all the case law, a lot of natural language understanding, and a lot of rules about how to apply all that knowledge, because sometimes case law is solid, sometimes you can bend it (especially if it is old, as interpretations change over time).
And finally, the law changes and adapts, not just in the book, but also in its interpretations. There are many famous examples of highest courts overruling their own 20-year old decision. Very often, such challenges to previous case law happen exactly because a judge decided to go against those established laws and he would rather take the risk of being overruled at the higher court than pass down a decision he does not stand behind. I wonder how you would model this ability in an NP-complete system?
To calculate the complexity of a system requires us to understand the inputs and outputs. The law, however, is an open system. Literally anything in its environment can influence it, especially changes on society and culture. Most countries have laws on the books that are rarely applied anymore because society has changed, but the law-making process lags behind. Laws against homosexuality are a current example. Or the death sentence, which in most countries had not been actually applied for years or decades before it was removed from the law books. And not because there were no cases where it could have been applied, but simply because judges did not apply it despite having the choice.
These environmental factors make a complexity estimate almost impossible, because we cannot enumerate them in a finite list unless we use all-quantors (e.g. "every kind of ..." or "all the ...")
New contributor
add a comment |
up vote
7
down vote
NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by n. In particular:
A problem is NP if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in n.
A problem is NP-complete if it is NP and moreover every NP problem can be reduced to it by a reduction process with runtime polynomial in n.
In the problem you propose, namely
Given this law book and this particular set of circumstances, is the defendant guilty?
I'm not sure what n is meant to be. It seems like the inputs here are the "set of circumstances" and the name of the defendant. Only the former could be of varying length, but then what do we even mean by the "set of circumstances"? Do we just feed in an arbitrary number of arbitrary facts like "the defendant owns purple socks" and "the judge had a sandwich for lunch today" or what? Moreover, are there constraints on these circumstances, or can we feed in a "circumstance" like "the barber of Seville shaves precisely those barbers who do not shave themselves"?
I don't think this question is well-posed, nor do I see any obvious way to make it well-posed.
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
add a comment |
up vote
2
down vote
I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce courts have to decide whether a marriage has "irretrievably broken down". There can never be an algorithm for deciding that question.
add a comment |
up vote
0
down vote
While some answers say it's undecidable, I suppose it's not what laws are for, as they are not enforceable.
If it's restricted in some ways that make it always decidable, it probably does not make much sense to talk about the actual complexity. It's because the inputs of laws as functions are generally not the definitions of events in the law, as in a card game, but evidences of events being legal or not.
There could be arbitrarily much evidences about a single event. For an event, there isn't an objective input length to make it possible to define the complexity. And for a given set of evidences, while there is an input length, the laws don't usually specify that someone must have a definite conclusion. They could, and usually prefer to try collecting more evidences even if the answer could be theoretically deduced logically in a difficult way. And a suspect could admit to something in a puzzling way to boost the complexity artificially if one has to work without evidences.
There would be more problems if cryptography is involved. They could theoretically reverse a strong encryption algorithm if they could compute for very long, but they may break the confidence of a signature algorithm to make it not usable as an evidence at the same time.
add a comment |
up vote
0
down vote
Jury members ultimately render verdicts based on applicable law given by judges to the jury to follow and the facts as determined by the jury using the factors in the jury instructions. Especially credibility of witnesses...who to believe.
Not reducible to an algorithm.
New contributor
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
add a comment |
7 Answers
7
active
oldest
votes
7 Answers
7
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
28
down vote
accepted
Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in practice the vast majority of criminal laws are simple decision trees.
Let's take, for example, section 187 (a) of the California penal code ("First Degree Murder").
(a) Murder is the unlawful killing of a human being, or a fetus, with
malice aforethought.
(b) This section shall not apply to any person
who commits an act that results in the death of a fetus if any of the
following apply:
(1) The act complied with the Therapeutic Abortion
Act, Article 2 (commencing with Section 123400) of Chapter 2 of Part 2
of Division 106 of the Health and Safety Code .
(2) The act was
committed by a holder of a physician's and surgeon's certificate, as
defined in the Business and Professions Code, in a case where, to a
medical certainty, the result of childbirth would be death of the
mother of the fetus or where her death from childbirth, although not
medically certain, would be substantially certain or more likely than
not.
(3) The act was solicited, aided, abetted, or consented to by the
mother of the fetus.
(c) Subdivision (b) shall not be construed to
prohibit the prosecution of any person under any other provision of
law.
This can be expressed as a simple set of boolean logic.
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)
Now there is of course a lot I trivialize here, like "what's malice forethought", "what is a therapeutic abortion" and "how do you determine the survival chance of a pregnancy". But these can also be expressed as similar boolean decision trees.
From a software engineering point of view, the legal system can be seen as a form of Business Rule Engine with the law being its ruleset.
That means that most laws have a computational complexity of c
. If you also take the process of evidence examination into account which is required to determine the values of all these boolean variables, then the complexity becomes n
where n
is the amount of evidence which needs to be evaluated.
However, sometimes laws include language which isn't decideable at all and requires an external oracle. For example, when it mentions concepts like "reasonable doubt". What is "reasonable"? That's for a court to decide.
New contributor
3
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
1
+1, but as Josiah alludes to,victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is sayingvictim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to justvictim.mom.survivalChance < 0.5
.
– ruakh
yesterday
3
Just a nitpick: if any of the following apply does not translate tox AND y AND z
butx OR y OR z
.
– Tomáš Zato
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
add a comment |
up vote
28
down vote
accepted
Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in practice the vast majority of criminal laws are simple decision trees.
Let's take, for example, section 187 (a) of the California penal code ("First Degree Murder").
(a) Murder is the unlawful killing of a human being, or a fetus, with
malice aforethought.
(b) This section shall not apply to any person
who commits an act that results in the death of a fetus if any of the
following apply:
(1) The act complied with the Therapeutic Abortion
Act, Article 2 (commencing with Section 123400) of Chapter 2 of Part 2
of Division 106 of the Health and Safety Code .
(2) The act was
committed by a holder of a physician's and surgeon's certificate, as
defined in the Business and Professions Code, in a case where, to a
medical certainty, the result of childbirth would be death of the
mother of the fetus or where her death from childbirth, although not
medically certain, would be substantially certain or more likely than
not.
(3) The act was solicited, aided, abetted, or consented to by the
mother of the fetus.
(c) Subdivision (b) shall not be construed to
prohibit the prosecution of any person under any other provision of
law.
This can be expressed as a simple set of boolean logic.
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)
Now there is of course a lot I trivialize here, like "what's malice forethought", "what is a therapeutic abortion" and "how do you determine the survival chance of a pregnancy". But these can also be expressed as similar boolean decision trees.
From a software engineering point of view, the legal system can be seen as a form of Business Rule Engine with the law being its ruleset.
That means that most laws have a computational complexity of c
. If you also take the process of evidence examination into account which is required to determine the values of all these boolean variables, then the complexity becomes n
where n
is the amount of evidence which needs to be evaluated.
However, sometimes laws include language which isn't decideable at all and requires an external oracle. For example, when it mentions concepts like "reasonable doubt". What is "reasonable"? That's for a court to decide.
New contributor
3
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
1
+1, but as Josiah alludes to,victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is sayingvictim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to justvictim.mom.survivalChance < 0.5
.
– ruakh
yesterday
3
Just a nitpick: if any of the following apply does not translate tox AND y AND z
butx OR y OR z
.
– Tomáš Zato
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
add a comment |
up vote
28
down vote
accepted
up vote
28
down vote
accepted
Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in practice the vast majority of criminal laws are simple decision trees.
Let's take, for example, section 187 (a) of the California penal code ("First Degree Murder").
(a) Murder is the unlawful killing of a human being, or a fetus, with
malice aforethought.
(b) This section shall not apply to any person
who commits an act that results in the death of a fetus if any of the
following apply:
(1) The act complied with the Therapeutic Abortion
Act, Article 2 (commencing with Section 123400) of Chapter 2 of Part 2
of Division 106 of the Health and Safety Code .
(2) The act was
committed by a holder of a physician's and surgeon's certificate, as
defined in the Business and Professions Code, in a case where, to a
medical certainty, the result of childbirth would be death of the
mother of the fetus or where her death from childbirth, although not
medically certain, would be substantially certain or more likely than
not.
(3) The act was solicited, aided, abetted, or consented to by the
mother of the fetus.
(c) Subdivision (b) shall not be construed to
prohibit the prosecution of any person under any other provision of
law.
This can be expressed as a simple set of boolean logic.
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)
Now there is of course a lot I trivialize here, like "what's malice forethought", "what is a therapeutic abortion" and "how do you determine the survival chance of a pregnancy". But these can also be expressed as similar boolean decision trees.
From a software engineering point of view, the legal system can be seen as a form of Business Rule Engine with the law being its ruleset.
That means that most laws have a computational complexity of c
. If you also take the process of evidence examination into account which is required to determine the values of all these boolean variables, then the complexity becomes n
where n
is the amount of evidence which needs to be evaluated.
However, sometimes laws include language which isn't decideable at all and requires an external oracle. For example, when it mentions concepts like "reasonable doubt". What is "reasonable"? That's for a court to decide.
New contributor
Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in practice the vast majority of criminal laws are simple decision trees.
Let's take, for example, section 187 (a) of the California penal code ("First Degree Murder").
(a) Murder is the unlawful killing of a human being, or a fetus, with
malice aforethought.
(b) This section shall not apply to any person
who commits an act that results in the death of a fetus if any of the
following apply:
(1) The act complied with the Therapeutic Abortion
Act, Article 2 (commencing with Section 123400) of Chapter 2 of Part 2
of Division 106 of the Health and Safety Code .
(2) The act was
committed by a holder of a physician's and surgeon's certificate, as
defined in the Business and Professions Code, in a case where, to a
medical certainty, the result of childbirth would be death of the
mother of the fetus or where her death from childbirth, although not
medically certain, would be substantially certain or more likely than
not.
(3) The act was solicited, aided, abetted, or consented to by the
mother of the fetus.
(c) Subdivision (b) shall not be construed to
prohibit the prosecution of any person under any other provision of
law.
This can be expressed as a simple set of boolean logic.
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)
Now there is of course a lot I trivialize here, like "what's malice forethought", "what is a therapeutic abortion" and "how do you determine the survival chance of a pregnancy". But these can also be expressed as similar boolean decision trees.
From a software engineering point of view, the legal system can be seen as a form of Business Rule Engine with the law being its ruleset.
That means that most laws have a computational complexity of c
. If you also take the process of evidence examination into account which is required to determine the values of all these boolean variables, then the complexity becomes n
where n
is the amount of evidence which needs to be evaluated.
However, sometimes laws include language which isn't decideable at all and requires an external oracle. For example, when it mentions concepts like "reasonable doubt". What is "reasonable"? That's for a court to decide.
New contributor
edited Nov 28 at 19:43
New contributor
answered Nov 28 at 9:57
Philipp
39616
39616
New contributor
New contributor
3
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
1
+1, but as Josiah alludes to,victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is sayingvictim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to justvictim.mom.survivalChance < 0.5
.
– ruakh
yesterday
3
Just a nitpick: if any of the following apply does not translate tox AND y AND z
butx OR y OR z
.
– Tomáš Zato
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
add a comment |
3
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
1
+1, but as Josiah alludes to,victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is sayingvictim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to justvictim.mom.survivalChance < 0.5
.
– ruakh
yesterday
3
Just a nitpick: if any of the following apply does not translate tox AND y AND z
butx OR y OR z
.
– Tomáš Zato
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
3
3
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
This is good. For your example I think some of the abortion related ANDs should be ORs - "any of the following". Also I don't see victim survival chance mentioned here.
– Josiah
yesterday
1
1
+1, but as Josiah alludes to,
victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is saying victim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to just victim.mom.survivalChance < 0.5
.– ruakh
yesterday
+1, but as Josiah alludes to,
victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5
is not a correct interpretation of the law; the law is saying victim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5
, which can be simplified to just victim.mom.survivalChance < 0.5
.– ruakh
yesterday
3
3
Just a nitpick: if any of the following apply does not translate to
x AND y AND z
but x OR y OR z
.– Tomáš Zato
12 hours ago
Just a nitpick: if any of the following apply does not translate to
x AND y AND z
but x OR y OR z
.– Tomáš Zato
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
I think there could be above-linear factors in the evidence, for example if you have to assess whether or not there exist two pieces of evidence which directly contradict each other. That's not what the legislation on the specific crime explicitly says, but it is what court procedure says.
– Steve Jessop
12 hours ago
add a comment |
up vote
88
down vote
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".
The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.
1
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
add a comment |
up vote
88
down vote
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".
The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.
1
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
add a comment |
up vote
88
down vote
up vote
88
down vote
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".
The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".
The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.
answered Nov 27 at 12:10
orlp
5,2761825
5,2761825
1
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
add a comment |
1
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
1
1
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.♦
Nov 28 at 8:09
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
Moderator notice (again): comments are not for extended discussion. If you wish to discuss this answer, use the chatroom. Any comment posted once a chatroom exists may be summarily deleted.
– Gilles♦
22 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill
– Hendrik Jan
8 hours ago
add a comment |
up vote
7
down vote
This is a very interesting question.
Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined rules.
Legalese actually defines its terms and thus many words (but not all!) used in the law actually do have precise meanings.
However, interpretation is where your approach of presenting a case to a logical system and getting a result will fail. The law is a generic definition that needs to be adapted to the specific case in question. Often this is a trivial, straightforward process, but there is no guarantee that it is and no non-trivial way to define the boundary.
A good example is self-defense. In most law systems, you can lawfully hurt another person provided that you are acting in self-defense. However, the wording is explicitly context-sensitive. For example, the british criminal law writes:
A person may use such force as is reasonable in the circumstances in the prevention of crime [...]
Case law defines what is "reasonable" in specific cases, but no general definition is on the books. There is also case law clearing up what exactly "prevention of crime" means. Since by definition a crime has not yet occurred, much less a court having decided that the action was, in fact, a crime, reasonable belief is enough in this particular case, but that is not actually written in the law!
To create a digital decision maker about the law, you would have to feed it not just the law itself, but also all the case law, a lot of natural language understanding, and a lot of rules about how to apply all that knowledge, because sometimes case law is solid, sometimes you can bend it (especially if it is old, as interpretations change over time).
And finally, the law changes and adapts, not just in the book, but also in its interpretations. There are many famous examples of highest courts overruling their own 20-year old decision. Very often, such challenges to previous case law happen exactly because a judge decided to go against those established laws and he would rather take the risk of being overruled at the higher court than pass down a decision he does not stand behind. I wonder how you would model this ability in an NP-complete system?
To calculate the complexity of a system requires us to understand the inputs and outputs. The law, however, is an open system. Literally anything in its environment can influence it, especially changes on society and culture. Most countries have laws on the books that are rarely applied anymore because society has changed, but the law-making process lags behind. Laws against homosexuality are a current example. Or the death sentence, which in most countries had not been actually applied for years or decades before it was removed from the law books. And not because there were no cases where it could have been applied, but simply because judges did not apply it despite having the choice.
These environmental factors make a complexity estimate almost impossible, because we cannot enumerate them in a finite list unless we use all-quantors (e.g. "every kind of ..." or "all the ...")
New contributor
add a comment |
up vote
7
down vote
This is a very interesting question.
Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined rules.
Legalese actually defines its terms and thus many words (but not all!) used in the law actually do have precise meanings.
However, interpretation is where your approach of presenting a case to a logical system and getting a result will fail. The law is a generic definition that needs to be adapted to the specific case in question. Often this is a trivial, straightforward process, but there is no guarantee that it is and no non-trivial way to define the boundary.
A good example is self-defense. In most law systems, you can lawfully hurt another person provided that you are acting in self-defense. However, the wording is explicitly context-sensitive. For example, the british criminal law writes:
A person may use such force as is reasonable in the circumstances in the prevention of crime [...]
Case law defines what is "reasonable" in specific cases, but no general definition is on the books. There is also case law clearing up what exactly "prevention of crime" means. Since by definition a crime has not yet occurred, much less a court having decided that the action was, in fact, a crime, reasonable belief is enough in this particular case, but that is not actually written in the law!
To create a digital decision maker about the law, you would have to feed it not just the law itself, but also all the case law, a lot of natural language understanding, and a lot of rules about how to apply all that knowledge, because sometimes case law is solid, sometimes you can bend it (especially if it is old, as interpretations change over time).
And finally, the law changes and adapts, not just in the book, but also in its interpretations. There are many famous examples of highest courts overruling their own 20-year old decision. Very often, such challenges to previous case law happen exactly because a judge decided to go against those established laws and he would rather take the risk of being overruled at the higher court than pass down a decision he does not stand behind. I wonder how you would model this ability in an NP-complete system?
To calculate the complexity of a system requires us to understand the inputs and outputs. The law, however, is an open system. Literally anything in its environment can influence it, especially changes on society and culture. Most countries have laws on the books that are rarely applied anymore because society has changed, but the law-making process lags behind. Laws against homosexuality are a current example. Or the death sentence, which in most countries had not been actually applied for years or decades before it was removed from the law books. And not because there were no cases where it could have been applied, but simply because judges did not apply it despite having the choice.
These environmental factors make a complexity estimate almost impossible, because we cannot enumerate them in a finite list unless we use all-quantors (e.g. "every kind of ..." or "all the ...")
New contributor
add a comment |
up vote
7
down vote
up vote
7
down vote
This is a very interesting question.
Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined rules.
Legalese actually defines its terms and thus many words (but not all!) used in the law actually do have precise meanings.
However, interpretation is where your approach of presenting a case to a logical system and getting a result will fail. The law is a generic definition that needs to be adapted to the specific case in question. Often this is a trivial, straightforward process, but there is no guarantee that it is and no non-trivial way to define the boundary.
A good example is self-defense. In most law systems, you can lawfully hurt another person provided that you are acting in self-defense. However, the wording is explicitly context-sensitive. For example, the british criminal law writes:
A person may use such force as is reasonable in the circumstances in the prevention of crime [...]
Case law defines what is "reasonable" in specific cases, but no general definition is on the books. There is also case law clearing up what exactly "prevention of crime" means. Since by definition a crime has not yet occurred, much less a court having decided that the action was, in fact, a crime, reasonable belief is enough in this particular case, but that is not actually written in the law!
To create a digital decision maker about the law, you would have to feed it not just the law itself, but also all the case law, a lot of natural language understanding, and a lot of rules about how to apply all that knowledge, because sometimes case law is solid, sometimes you can bend it (especially if it is old, as interpretations change over time).
And finally, the law changes and adapts, not just in the book, but also in its interpretations. There are many famous examples of highest courts overruling their own 20-year old decision. Very often, such challenges to previous case law happen exactly because a judge decided to go against those established laws and he would rather take the risk of being overruled at the higher court than pass down a decision he does not stand behind. I wonder how you would model this ability in an NP-complete system?
To calculate the complexity of a system requires us to understand the inputs and outputs. The law, however, is an open system. Literally anything in its environment can influence it, especially changes on society and culture. Most countries have laws on the books that are rarely applied anymore because society has changed, but the law-making process lags behind. Laws against homosexuality are a current example. Or the death sentence, which in most countries had not been actually applied for years or decades before it was removed from the law books. And not because there were no cases where it could have been applied, but simply because judges did not apply it despite having the choice.
These environmental factors make a complexity estimate almost impossible, because we cannot enumerate them in a finite list unless we use all-quantors (e.g. "every kind of ..." or "all the ...")
New contributor
This is a very interesting question.
Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined rules.
Legalese actually defines its terms and thus many words (but not all!) used in the law actually do have precise meanings.
However, interpretation is where your approach of presenting a case to a logical system and getting a result will fail. The law is a generic definition that needs to be adapted to the specific case in question. Often this is a trivial, straightforward process, but there is no guarantee that it is and no non-trivial way to define the boundary.
A good example is self-defense. In most law systems, you can lawfully hurt another person provided that you are acting in self-defense. However, the wording is explicitly context-sensitive. For example, the british criminal law writes:
A person may use such force as is reasonable in the circumstances in the prevention of crime [...]
Case law defines what is "reasonable" in specific cases, but no general definition is on the books. There is also case law clearing up what exactly "prevention of crime" means. Since by definition a crime has not yet occurred, much less a court having decided that the action was, in fact, a crime, reasonable belief is enough in this particular case, but that is not actually written in the law!
To create a digital decision maker about the law, you would have to feed it not just the law itself, but also all the case law, a lot of natural language understanding, and a lot of rules about how to apply all that knowledge, because sometimes case law is solid, sometimes you can bend it (especially if it is old, as interpretations change over time).
And finally, the law changes and adapts, not just in the book, but also in its interpretations. There are many famous examples of highest courts overruling their own 20-year old decision. Very often, such challenges to previous case law happen exactly because a judge decided to go against those established laws and he would rather take the risk of being overruled at the higher court than pass down a decision he does not stand behind. I wonder how you would model this ability in an NP-complete system?
To calculate the complexity of a system requires us to understand the inputs and outputs. The law, however, is an open system. Literally anything in its environment can influence it, especially changes on society and culture. Most countries have laws on the books that are rarely applied anymore because society has changed, but the law-making process lags behind. Laws against homosexuality are a current example. Or the death sentence, which in most countries had not been actually applied for years or decades before it was removed from the law books. And not because there were no cases where it could have been applied, but simply because judges did not apply it despite having the choice.
These environmental factors make a complexity estimate almost impossible, because we cannot enumerate them in a finite list unless we use all-quantors (e.g. "every kind of ..." or "all the ...")
New contributor
New contributor
answered Nov 28 at 12:12
Tom
1712
1712
New contributor
New contributor
add a comment |
add a comment |
up vote
7
down vote
NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by n. In particular:
A problem is NP if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in n.
A problem is NP-complete if it is NP and moreover every NP problem can be reduced to it by a reduction process with runtime polynomial in n.
In the problem you propose, namely
Given this law book and this particular set of circumstances, is the defendant guilty?
I'm not sure what n is meant to be. It seems like the inputs here are the "set of circumstances" and the name of the defendant. Only the former could be of varying length, but then what do we even mean by the "set of circumstances"? Do we just feed in an arbitrary number of arbitrary facts like "the defendant owns purple socks" and "the judge had a sandwich for lunch today" or what? Moreover, are there constraints on these circumstances, or can we feed in a "circumstance" like "the barber of Seville shaves precisely those barbers who do not shave themselves"?
I don't think this question is well-posed, nor do I see any obvious way to make it well-posed.
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
add a comment |
up vote
7
down vote
NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by n. In particular:
A problem is NP if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in n.
A problem is NP-complete if it is NP and moreover every NP problem can be reduced to it by a reduction process with runtime polynomial in n.
In the problem you propose, namely
Given this law book and this particular set of circumstances, is the defendant guilty?
I'm not sure what n is meant to be. It seems like the inputs here are the "set of circumstances" and the name of the defendant. Only the former could be of varying length, but then what do we even mean by the "set of circumstances"? Do we just feed in an arbitrary number of arbitrary facts like "the defendant owns purple socks" and "the judge had a sandwich for lunch today" or what? Moreover, are there constraints on these circumstances, or can we feed in a "circumstance" like "the barber of Seville shaves precisely those barbers who do not shave themselves"?
I don't think this question is well-posed, nor do I see any obvious way to make it well-posed.
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
add a comment |
up vote
7
down vote
up vote
7
down vote
NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by n. In particular:
A problem is NP if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in n.
A problem is NP-complete if it is NP and moreover every NP problem can be reduced to it by a reduction process with runtime polynomial in n.
In the problem you propose, namely
Given this law book and this particular set of circumstances, is the defendant guilty?
I'm not sure what n is meant to be. It seems like the inputs here are the "set of circumstances" and the name of the defendant. Only the former could be of varying length, but then what do we even mean by the "set of circumstances"? Do we just feed in an arbitrary number of arbitrary facts like "the defendant owns purple socks" and "the judge had a sandwich for lunch today" or what? Moreover, are there constraints on these circumstances, or can we feed in a "circumstance" like "the barber of Seville shaves precisely those barbers who do not shave themselves"?
I don't think this question is well-posed, nor do I see any obvious way to make it well-posed.
NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by n. In particular:
A problem is NP if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in n.
A problem is NP-complete if it is NP and moreover every NP problem can be reduced to it by a reduction process with runtime polynomial in n.
In the problem you propose, namely
Given this law book and this particular set of circumstances, is the defendant guilty?
I'm not sure what n is meant to be. It seems like the inputs here are the "set of circumstances" and the name of the defendant. Only the former could be of varying length, but then what do we even mean by the "set of circumstances"? Do we just feed in an arbitrary number of arbitrary facts like "the defendant owns purple socks" and "the judge had a sandwich for lunch today" or what? Moreover, are there constraints on these circumstances, or can we feed in a "circumstance" like "the barber of Seville shaves precisely those barbers who do not shave themselves"?
I don't think this question is well-posed, nor do I see any obvious way to make it well-posed.
answered Nov 28 at 20:08
Daniel McLaury
21613
21613
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
add a comment |
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
Before the trial the justice system conducts a preliminary investigation (not sure if that is the proper English word) in which all relevant circumstances are collected. The size of the documents collecting these circumstances depend on the complexity of the crime - for simple cases only a few dozen pages and for complex ones (eg Microsoft antitrust), tens of thousands of pages or more.
– Björn Lindqvist
17 hours ago
add a comment |
up vote
2
down vote
I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce courts have to decide whether a marriage has "irretrievably broken down". There can never be an algorithm for deciding that question.
add a comment |
up vote
2
down vote
I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce courts have to decide whether a marriage has "irretrievably broken down". There can never be an algorithm for deciding that question.
add a comment |
up vote
2
down vote
up vote
2
down vote
I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce courts have to decide whether a marriage has "irretrievably broken down". There can never be an algorithm for deciding that question.
I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce courts have to decide whether a marriage has "irretrievably broken down". There can never be an algorithm for deciding that question.
answered 2 days ago
Michael Kay
37913
37913
add a comment |
add a comment |
up vote
0
down vote
While some answers say it's undecidable, I suppose it's not what laws are for, as they are not enforceable.
If it's restricted in some ways that make it always decidable, it probably does not make much sense to talk about the actual complexity. It's because the inputs of laws as functions are generally not the definitions of events in the law, as in a card game, but evidences of events being legal or not.
There could be arbitrarily much evidences about a single event. For an event, there isn't an objective input length to make it possible to define the complexity. And for a given set of evidences, while there is an input length, the laws don't usually specify that someone must have a definite conclusion. They could, and usually prefer to try collecting more evidences even if the answer could be theoretically deduced logically in a difficult way. And a suspect could admit to something in a puzzling way to boost the complexity artificially if one has to work without evidences.
There would be more problems if cryptography is involved. They could theoretically reverse a strong encryption algorithm if they could compute for very long, but they may break the confidence of a signature algorithm to make it not usable as an evidence at the same time.
add a comment |
up vote
0
down vote
While some answers say it's undecidable, I suppose it's not what laws are for, as they are not enforceable.
If it's restricted in some ways that make it always decidable, it probably does not make much sense to talk about the actual complexity. It's because the inputs of laws as functions are generally not the definitions of events in the law, as in a card game, but evidences of events being legal or not.
There could be arbitrarily much evidences about a single event. For an event, there isn't an objective input length to make it possible to define the complexity. And for a given set of evidences, while there is an input length, the laws don't usually specify that someone must have a definite conclusion. They could, and usually prefer to try collecting more evidences even if the answer could be theoretically deduced logically in a difficult way. And a suspect could admit to something in a puzzling way to boost the complexity artificially if one has to work without evidences.
There would be more problems if cryptography is involved. They could theoretically reverse a strong encryption algorithm if they could compute for very long, but they may break the confidence of a signature algorithm to make it not usable as an evidence at the same time.
add a comment |
up vote
0
down vote
up vote
0
down vote
While some answers say it's undecidable, I suppose it's not what laws are for, as they are not enforceable.
If it's restricted in some ways that make it always decidable, it probably does not make much sense to talk about the actual complexity. It's because the inputs of laws as functions are generally not the definitions of events in the law, as in a card game, but evidences of events being legal or not.
There could be arbitrarily much evidences about a single event. For an event, there isn't an objective input length to make it possible to define the complexity. And for a given set of evidences, while there is an input length, the laws don't usually specify that someone must have a definite conclusion. They could, and usually prefer to try collecting more evidences even if the answer could be theoretically deduced logically in a difficult way. And a suspect could admit to something in a puzzling way to boost the complexity artificially if one has to work without evidences.
There would be more problems if cryptography is involved. They could theoretically reverse a strong encryption algorithm if they could compute for very long, but they may break the confidence of a signature algorithm to make it not usable as an evidence at the same time.
While some answers say it's undecidable, I suppose it's not what laws are for, as they are not enforceable.
If it's restricted in some ways that make it always decidable, it probably does not make much sense to talk about the actual complexity. It's because the inputs of laws as functions are generally not the definitions of events in the law, as in a card game, but evidences of events being legal or not.
There could be arbitrarily much evidences about a single event. For an event, there isn't an objective input length to make it possible to define the complexity. And for a given set of evidences, while there is an input length, the laws don't usually specify that someone must have a definite conclusion. They could, and usually prefer to try collecting more evidences even if the answer could be theoretically deduced logically in a difficult way. And a suspect could admit to something in a puzzling way to boost the complexity artificially if one has to work without evidences.
There would be more problems if cryptography is involved. They could theoretically reverse a strong encryption algorithm if they could compute for very long, but they may break the confidence of a signature algorithm to make it not usable as an evidence at the same time.
answered yesterday
user23013
38819
38819
add a comment |
add a comment |
up vote
0
down vote
Jury members ultimately render verdicts based on applicable law given by judges to the jury to follow and the facts as determined by the jury using the factors in the jury instructions. Especially credibility of witnesses...who to believe.
Not reducible to an algorithm.
New contributor
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
add a comment |
up vote
0
down vote
Jury members ultimately render verdicts based on applicable law given by judges to the jury to follow and the facts as determined by the jury using the factors in the jury instructions. Especially credibility of witnesses...who to believe.
Not reducible to an algorithm.
New contributor
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
add a comment |
up vote
0
down vote
up vote
0
down vote
Jury members ultimately render verdicts based on applicable law given by judges to the jury to follow and the facts as determined by the jury using the factors in the jury instructions. Especially credibility of witnesses...who to believe.
Not reducible to an algorithm.
New contributor
Jury members ultimately render verdicts based on applicable law given by judges to the jury to follow and the facts as determined by the jury using the factors in the jury instructions. Especially credibility of witnesses...who to believe.
Not reducible to an algorithm.
New contributor
New contributor
answered 13 hours ago
Tom Whitaker Jr
1
1
New contributor
New contributor
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
add a comment |
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
This seems to be a rather philosophical anwer, as opposed to a computer science one. That doesn't make it wrong, but probably not helpful for a question asked on this site.
– Raphael♦
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
Depends on whether cs considers the ground truth of an application and whether it is feasible or not. At the moment, any discussion without inclusion of AI touchpoints seems off course. But that's from a 35+ yr trial atty and not a cs guru.
– Tom Whitaker Jr
13 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law.
– Apass.Jack
12 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
@TomWhitakerJr My perspective, for the purpose of maintaining the scope of this site, is that while applying CS techniques should be bound by ethical/philosophical considerations, the study of those techniques is not. I'm fully aware that long discussions lie there, but I simply don't see how we can make this site work equally well for technical and ethical/philosophical questions. So while I fully agree that discussions such as how AI should be used must be held somewhere, I don't think this site it the place for it.
– Raphael♦
10 hours ago
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f100599%2fis-legislation-np-complete%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
14
Your claim about MtG can't be correct, since there are decidable problems that aren't in NP. So I guess you mean that some part of the game is NP-complete, and some other part is Turing-complete.
– David Richerby
Nov 27 at 13:32
7
A professor of mine published a few works on formal analysis of legislation, like this, this and this. I don't think it's quite what you're asking but just in case you find it relevant.
– jdehesa
Nov 27 at 15:08
The complexity class called "lawyers are capable of infinite complexity." ;) If you're interested in formal analysis of some arbitrarily defined abstract structure that's designed to approximate the law codes in some specific ways, that formal analysis may be possible. However, it's important to recognize that it won't relate in any meaningful way to actual court cases and the actual justice system, even in an idealized world. Intent matters, and a large part of court cases is establishing what the circumstances are in the first place.
– Wildcard
Nov 28 at 0:11
6
It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
Nov 29 at 2:46
1
A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject.
– Dmitri Chubarov
20 hours ago