# Is legislation NP-complete?

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?

• 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. Nov 27 '18 at 13:32
• 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. Nov 27 '18 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. Nov 28 '18 at 0:11
• It depends entirely on whether or not the computation time is billable. Nov 29 '18 at 2:46
• A quick reference on MtG complexity could be a Chatterjee & Ibsen-Jensen, 1998. Surely there are other papers on the subject. Dec 1 '18 at 11:39

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 !(     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.

• 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. Nov 30 '18 at 20:51
• +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. Dec 1 '18 at 6:43
• Just a nitpick: if any of the following apply does not translate to x AND y AND z but x OR y OR z. Dec 1 '18 at 19:03
• If it were this simple, why do we have judges? Why do we care so much who they are? Why do we have jurisprudence? Why are there so many controversial court cases? Clearly, law is not as simple as you make it out to be. Reasonable doubt is a good example of a problematic part (which occurs quite frequently), another would be constructing a narrative from an arbitrary set of evidence or even deciding on the length of a prison sentence. Dec 2 '18 at 11:27
• It's even worse. Not only can legal language include arbitrary language. It can also not include implicit assumptions. So it can in theory be infinitly complex. Also human language is so complex and implicit, that you can ask the definition of any word in any sentence, prompting someone to explain it. This can also go on for ever. In other words, communication and anything that is expressed in communication, isn't even guranteed to make sense, be well defined or ever terminate, when executed. Dec 2 '18 at 15:59

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.

• Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.
Nov 28 '18 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. Dec 1 '18 at 9:07
• It might be even worse than undecidable, meaning not properly defined or self-contradictory. Remember the Indiana Pi Bill Dec 1 '18 at 23:53

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.

• 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. Dec 1 '18 at 14:31

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.

• 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
Dec 1 '18 at 18:37
• 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. Dec 1 '18 at 18:43
• This answer is a nice reminder of how far is cs computability or decidability theory from the practice of law. Dec 1 '18 at 19:33
• @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
Dec 1 '18 at 21:51