Is legislation NP-complete?











up vote
53
down vote

favorite
14












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?










share|cite|improve this question




















  • 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















up vote
53
down vote

favorite
14












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?










share|cite|improve this question




















  • 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













up vote
53
down vote

favorite
14









up vote
53
down vote

favorite
14






14





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?










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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














  • 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










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.






share|cite|improve this answer










New contributor




Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.














  • 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 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




    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




















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.






share|cite|improve this answer

















  • 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


















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 ...")






share|cite|improve this answer








New contributor




Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

























    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.






    share|cite|improve this answer





















    • 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


















    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.






    share|cite|improve this answer




























      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.






      share|cite|improve this answer




























        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.






        share|cite|improve this answer








        New contributor




        Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.


















        • 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











        Your Answer





        StackExchange.ifUsing("editor", function () {
        return StackExchange.using("mathjaxEditing", function () {
        StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
        StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
        });
        });
        }, "mathjax-editing");

        StackExchange.ready(function() {
        var channelOptions = {
        tags: "".split(" "),
        id: "419"
        };
        initTagRenderer("".split(" "), "".split(" "), channelOptions);

        StackExchange.using("externalEditor", function() {
        // Have to fire editor after snippets, if snippets enabled
        if (StackExchange.settings.snippets.snippetsEnabled) {
        StackExchange.using("snippets", function() {
        createEditor();
        });
        }
        else {
        createEditor();
        }
        });

        function createEditor() {
        StackExchange.prepareEditor({
        heartbeatType: 'answer',
        convertImagesToLinks: false,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: null,
        bindNavPrevention: true,
        postfix: "",
        imageUploader: {
        brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
        contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
        allowUrls: true
        },
        onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        });


        }
        });














        draft saved

        draft discarded


















        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

























        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.






        share|cite|improve this answer










        New contributor




        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.














        • 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 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




          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

















        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.






        share|cite|improve this answer










        New contributor




        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.














        • 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 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




          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















        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.






        share|cite|improve this answer










        New contributor




        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        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.







        share|cite|improve this answer










        New contributor




        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        share|cite|improve this answer



        share|cite|improve this answer








        edited Nov 28 at 19:43





















        New contributor




        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        answered Nov 28 at 9:57









        Philipp

        39616




        39616




        New contributor




        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.





        New contributor





        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






        Philipp is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.








        • 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 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




          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
















        • 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 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




          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










        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












        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.






        share|cite|improve this answer

















        • 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















        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.






        share|cite|improve this answer

















        • 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













        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.






        share|cite|improve this answer












        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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        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














        • 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










        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 ...")






        share|cite|improve this answer








        New contributor




        Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






















          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 ...")






          share|cite|improve this answer








          New contributor




          Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.




















            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 ...")






            share|cite|improve this answer








            New contributor




            Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.









            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 ...")







            share|cite|improve this answer








            New contributor




            Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.









            share|cite|improve this answer



            share|cite|improve this answer






            New contributor




            Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.









            answered Nov 28 at 12:12









            Tom

            1712




            1712




            New contributor




            Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.





            New contributor





            Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.






            Tom is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.






















                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.






                share|cite|improve this answer





















                • 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















                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.






                share|cite|improve this answer





















                • 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













                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.






                share|cite|improve this answer












                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.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                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


















                • 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










                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.






                share|cite|improve this answer

























                  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.






                  share|cite|improve this answer























                    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.






                    share|cite|improve this answer












                    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.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 2 days ago









                    Michael Kay

                    37913




                    37913






















                        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.






                        share|cite|improve this answer

























                          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.






                          share|cite|improve this answer























                            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.






                            share|cite|improve this answer












                            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.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered yesterday









                            user23013

                            38819




                            38819






















                                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.






                                share|cite|improve this answer








                                New contributor




                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.


















                                • 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















                                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.






                                share|cite|improve this answer








                                New contributor




                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.


















                                • 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













                                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.






                                share|cite|improve this answer








                                New contributor




                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.









                                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.







                                share|cite|improve this answer








                                New contributor




                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.









                                share|cite|improve this answer



                                share|cite|improve this answer






                                New contributor




                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.









                                answered 13 hours ago









                                Tom Whitaker Jr

                                1




                                1




                                New contributor




                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.





                                New contributor





                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.






                                Tom Whitaker Jr is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                Check out our Code of Conduct.












                                • 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










                                • 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


















                                draft saved

                                draft discarded




















































                                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.




                                draft saved


                                draft discarded














                                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





















































                                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







                                Popular posts from this blog

                                數位音樂下載

                                格利澤436b

                                When can things happen in Etherscan, such as the picture below?