Is legislation NP-complete?











up vote
46
down vote

favorite
10












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




















  • 13




    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






  • 5




    It depends entirely on whether or not the computation time is billable.
    – Matt Timmermans
    2 days ago










  • Those in the legal profession can make something really complex in a hurry
    – dalearn
    10 hours ago















up vote
46
down vote

favorite
10












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




















  • 13




    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






  • 5




    It depends entirely on whether or not the computation time is billable.
    – Matt Timmermans
    2 days ago










  • Those in the legal profession can make something really complex in a hurry
    – dalearn
    10 hours ago













up vote
46
down vote

favorite
10









up vote
46
down vote

favorite
10






10





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 2 days ago









Juho

15.1k54089




15.1k54089










asked Nov 27 at 11:46









Björn Lindqvist

389139




389139








  • 13




    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






  • 5




    It depends entirely on whether or not the computation time is billable.
    – Matt Timmermans
    2 days ago










  • Those in the legal profession can make something really complex in a hurry
    – dalearn
    10 hours ago














  • 13




    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






  • 5




    It depends entirely on whether or not the computation time is billable.
    – Matt Timmermans
    2 days ago










  • Those in the legal profession can make something really complex in a hurry
    – dalearn
    10 hours ago








13




13




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




5




5




It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
2 days ago




It depends entirely on whether or not the computation time is billable.
– Matt Timmermans
2 days ago












Those in the legal profession can make something really complex in a hurry
– dalearn
10 hours ago




Those in the legal profession can make something really complex in a hurry
– dalearn
10 hours ago










6 Answers
6






active

oldest

votes

















up vote
85
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
    4 hours ago


















up vote
24
down vote













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.














  • 2




    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
    16 hours ago








  • 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
    6 hours ago




















up vote
6
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
    6
    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




























      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





















          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

























          6 Answers
          6






          active

          oldest

          votes








          6 Answers
          6






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          85
          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
            4 hours ago















          up vote
          85
          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
            4 hours ago













          up vote
          85
          down vote










          up vote
          85
          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,246825




          5,246825








          • 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
            4 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
            4 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
          4 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
          4 hours ago










          up vote
          24
          down vote













          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.














          • 2




            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
            16 hours ago








          • 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
            6 hours ago

















          up vote
          24
          down vote













          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.














          • 2




            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
            16 hours ago








          • 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
            6 hours ago















          up vote
          24
          down vote










          up vote
          24
          down vote









          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 2 days ago





















          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

          3416




          3416




          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.








          • 2




            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
            16 hours ago








          • 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
            6 hours ago
















          • 2




            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
            16 hours ago








          • 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
            6 hours ago










          2




          2




          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
          16 hours ago






          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
          16 hours ago






          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
          6 hours ago






          +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
          6 hours ago












          up vote
          6
          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
            6
            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
              6
              down vote










              up vote
              6
              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

              1612




              1612




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

























                    up vote
                    6
                    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























                      up vote
                      6
                      down vote










                      up vote
                      6
                      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 2 days ago









                      Daniel McLaury

                      20613




                      20613






















                          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






























                                          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

                                          AnyDesk - Fatal Program Failure

                                          How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

                                          QoS: MAC-Priority for clients behind a repeater