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?
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.
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.
$\endgroup$
x AND y AND z but x OR y OR z.
$\endgroup$
Commented
Dec 1, 2018 at 19:03
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.
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 ...")
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.
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.
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.
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.
