Apakah undang-undang NP-lengkap?

64

Saya ingin tahu apakah ada pekerjaan yang menghubungkan kode hukum dengan kompleksitas. Secara khusus, misalkan kita memiliki masalah keputusan "Mengingat buku hukum ini dan keadaan khusus ini, apakah terdakwa bersalah?" Kelas kompleksitas apa yang dimilikinya?

Ada hasil yang telah membuktikan bahwa permainan kartu Magic: the Gathering adalah NP dan Turing-complete jadi bukankah seharusnya hasil yang sama ada untuk kode hukum?

Björn Lindqvist
sumber
18
Klaim Anda tentang MtG tidak dapat benar, karena ada masalah yang tidak dapat dipisahkan yang tidak ada dalam NP . Jadi saya kira maksud Anda beberapa bagian dari permainan ini adalah NP -complete, dan beberapa bagian lainnya adalah Turing-complete.
David Richerby
8
Seorang profesor saya menerbitkan beberapa karya tentang analisis formal undang-undang, seperti ini , ini dan ini . Saya tidak berpikir itu yang Anda tanyakan tetapi kalau-kalau Anda menganggapnya relevan.
jdehesa
1
Kelas kompleksitas yang disebut "pengacara mampu kompleksitas yang tak terbatas." ;) Jika Anda tertarik pada analisis formal dari beberapa struktur abstrak yang ditentukan secara sewenang-wenang yang dirancang untuk memperkirakan kode hukum dalam beberapa cara tertentu, analisis formal itu mungkin dilakukan. Namun, penting untuk menyadari bahwa itu tidak akan berhubungan dengan cara apa pun yang berarti dengan kasus-kasus pengadilan aktual dan sistem peradilan yang sebenarnya , bahkan di dunia yang ideal sekalipun. Hal niat, dan sebagian besar dari kasus pengadilan adalah membangun apa keadaan yang di tempat pertama.
Wildcard
9
Itu sepenuhnya tergantung pada apakah waktu perhitungan dapat ditagih atau tidak.
Matt Timmermans
1
Referensi cepat tentang kompleksitas MtG bisa berupa Chatterjee & Ibsen-Jensen, 1998 . Tentunya ada makalah lain tentang masalah ini.
Dmitri Chubarov

Jawaban:

33

Hukum dapat mencakup bahasa arbitrer, dan bahasa arbitrer mampu mengekspresikan logika NP-complete. Jadi secara teori akan mungkin untuk membuat NP-lengkap atau bahkan hukum yang tidak dapat ditentukan. Namun, dalam praktiknya sebagian besar hukum pidana adalah pohon keputusan sederhana.

Mari kita ambil, misalnya, bagian 187 (a) dari hukum pidana California ("Pembunuhan Tingkat Pertama").

(a) Pembunuhan adalah pembunuhan tidak sah terhadap manusia, atau janin, dengan kejahatan yang telah dipikirkan sebelumnya.

(B) Bagian ini tidak berlaku untuk orang yang melakukan tindakan yang mengakibatkan kematian janin jika salah satu dari berikut berlaku:

(1) Undang-undang tersebut memenuhi Undang-Undang Aborsi Terapi, Pasal 2 (dimulai dengan Bagian 123400) dari Bab 2 Bagian 2 dari Bagian 106 dari Kode Kesehatan dan Keselamatan.

(2) Tindakan tersebut dilakukan oleh pemegang sertifikat dokter dan ahli bedah, sebagaimana didefinisikan dalam Kode Bisnis dan Profesi, dalam kasus di mana, untuk kepastian medis, hasil persalinan adalah kematian ibu dari janin atau di mana kematiannya sejak melahirkan, meskipun tidak pasti secara medis, akan jauh lebih pasti atau lebih mungkin daripada tidak.

(3) Tindakan itu diminta, dibantu, bersekongkol, atau disetujui oleh ibu janin.

(c) Subdivisi (b) tidak akan ditafsirkan untuk melarang penuntutan terhadap siapa pun berdasarkan ketentuan hukum lainnya.

Ini dapat dinyatakan sebagai seperangkat logika boolean sederhana.

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)

Sekarang tentu saja ada banyak hal yang saya anggap remeh di sini, seperti "apa yang telah dipikirkan sebelumnya", "apa itu aborsi terapeutik" dan "bagaimana Anda menentukan peluang kelangsungan hidup kehamilan". Tetapi ini juga dapat dinyatakan sebagai pohon keputusan boolean yang serupa.

Dari sudut pandang rekayasa perangkat lunak, sistem hukum dapat dilihat sebagai bentuk Business Rule Engine dengan undang-undang sebagai peraturannya.

Itu berarti bahwa sebagian besar undang-undang memiliki kompleksitas komputasi c. Jika Anda juga mempertimbangkan proses pemeriksaan bukti yang diperlukan untuk menentukan nilai-nilai semua variabel boolean ini, maka kompleksitasnya menjadi di nmana njumlah bukti yang perlu dievaluasi.

Namun, terkadang undang-undang menyertakan bahasa yang tidak dapat diputuskan sama sekali dan membutuhkan oracle eksternal. Misalnya, ketika menyebutkan konsep seperti "keraguan yang masuk akal". Apa itu "masuk akal"? Itu yang harus diputuskan oleh pengadilan.

Philipp
sumber
4
Ini bagus. Sebagai contoh Anda, saya pikir beberapa AND terkait aborsi harus OR - "salah satu dari yang berikut". Saya juga tidak melihat peluang bertahan hidup korban disebutkan di sini.
Josiah
1
+1, tetapi seperti yang disinggung oleh Yosia, victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5bukanlah penafsiran hukum yang benar; hukum mengatakan victim.mom.survivalChance == 0 OR victim.mom.survivalChance > 0 AND victim.mom.survivalChance < 0.5, yang dapat disederhanakan menjadi adil victim.mom.survivalChance < 0.5.
ruakh
4
Just a nitpick: jika salah satu dari yang berikut ini berlaku tidak diterjemahkan menjadi x AND y AND ztetapi x OR y OR z.
Tomáš Zato
3
Jika sesederhana ini, mengapa kita memiliki hakim? Mengapa kita begitu peduli siapa mereka? Mengapa kami memiliki yurisprudensi? Mengapa ada begitu banyak kasus pengadilan yang kontroversial? Jelas, hukum tidak sesederhana seperti yang Anda bayangkan. Keraguan yang masuk akal adalah contoh yang baik dari bagian yang bermasalah (yang cukup sering terjadi), yang lain akan membangun narasi dari set bukti yang sewenang-wenang atau bahkan memutuskan panjangnya hukuman penjara.
11684
1
Ini bahkan lebih buruk. Tidak hanya bahasa hukum dapat mencakup bahasa arbitrer. Itu juga tidak bisa memasukkan asumsi implisit. Jadi secara teori bisa sangat rumit. Bahasa manusia juga sangat kompleks dan implisit, sehingga Anda dapat menanyakan definisi kata apa pun dalam kalimat apa pun, mendorong seseorang untuk menjelaskannya. Ini juga bisa berlangsung selamanya. Dengan kata lain, komunikasi dan segala sesuatu yang dinyatakan dalam komunikasi, bahkan tidak dijamin masuk akal, tidak didefinisikan dengan baik atau pernah berakhir, ketika dieksekusi.
Semoga bermanfaat
95

Ini tidak dapat dipastikan karena sebuah buku hukum dapat memasukkan logika sewenang-wenang. Contoh konyol hukum penyensoran adalah "ilegal mempublikasikan program komputer apa pun yang tidak berhenti".

Alasan mengapa hasil MTG ada dan menarik adalah karena MTG memiliki satu set tetap (sebagian besar) aturan yang tidak ambigu, tidak seperti undang-undang yang terus berubah, sangat terlokalisir, dan ambigu tanpa henti.

orlp
sumber
1
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
DW
Pemberitahuan moderator (lagi): komentar tidak untuk diskusi panjang. Jika Anda ingin mendiskusikan jawaban ini, gunakan ruang obrolan . Setiap komentar yang diposting setelah ruang obrolan ada dapat dengan cepat dihapus.
Gilles 'SO- berhenti menjadi jahat'
3
Ini mungkin bahkan lebih buruk dari yang tidak dapat dipikirkan, artinya tidak didefinisikan dengan benar atau bertentangan dengan diri sendiri. Ingat Pi Pi Indiana
Hendrik
10

Ini pertanyaan yang sangat menarik.

Hukum ada di suatu tempat antara bahasa sehari-hari dengan aturannya yang sewenang-wenang, terus berubah, dan sering kali lunak, dan bahasa pemrograman dengan aturannya yang sangat spesifik dan terdefinisi.

Legalese sebenarnya mendefinisikan istilah-istilahnya dan dengan demikian banyak kata (tetapi tidak semua!) Yang digunakan dalam hukum sebenarnya memiliki makna yang tepat.

Namun, interpretasi adalah di mana pendekatan Anda dalam menyajikan kasus ke sistem logis dan mendapatkan hasilnya akan gagal. Undang-undang adalah definisi umum yang perlu disesuaikan dengan kasus spesifik yang dipermasalahkan. Seringkali ini adalah proses yang mudah dan sepele, tetapi tidak ada jaminan bahwa itu dan tidak ada cara yang tidak sepele untuk mendefinisikan batas.

Contoh yang baik adalah pertahanan diri. Dalam kebanyakan sistem hukum, Anda dapat melukai orang lain asalkan Anda bertindak membela diri. Namun, kata-katanya secara eksplisit peka konteks. Sebagai contoh, hukum pidana Inggris menulis:

Seseorang dapat menggunakan kekuatan seperti itu wajar dalam situasi dalam pencegahan kejahatan [...]

Hukum kasus mendefinisikan apa yang "masuk akal" dalam kasus-kasus tertentu , tetapi tidak ada definisi umum tentang buku-buku tersebut. Ada juga hukum kasus yang menjelaskan apa sebenarnya arti "pencegahan kejahatan". Karena definisi kejahatan belum terjadi, apalagi pengadilan memutuskan bahwa tindakan itu, pada kenyataannya, kejahatan, kepercayaan yang cukup sudah cukup dalam kasus khusus ini, tetapi itu sebenarnya tidak tertulis dalam hukum!

Untuk membuat pembuat keputusan digital tentang hukum, Anda harus memberinya bukan hanya hukum itu sendiri, tetapi juga semua hukum kasus, banyak pemahaman bahasa alami, dan banyak aturan tentang cara menerapkan semua pengetahuan itu, karena kadang-kadang hukum kasus itu solid, kadang-kadang Anda bisa membengkokkannya (terutama jika sudah tua, karena interpretasi berubah seiring waktu).

Dan akhirnya, hukum berubah dan beradaptasi, tidak hanya dalam buku, tetapi juga dalam interpretasinya. Ada banyak contoh terkenal dari pengadilan tertinggi yang menolak keputusan mereka sendiri yang berusia 20 tahun. Sangat sering, tantangan seperti itu terhadap hukum kasus sebelumnya terjadi justru karena seorang hakim memutuskan untuk melawan hukum-hukum yang sudah ada dan ia lebih suka mengambil risiko ditolak di pengadilan yang lebih tinggi daripada menjatuhkan keputusan yang tidak ia tahan. Saya bertanya-tanya bagaimana Anda akan memodelkan kemampuan ini dalam sistem NP-complete?

Untuk menghitung kompleksitas suatu sistem mengharuskan kita untuk memahami input dan output. Namun, hukum adalah sistem terbuka. Secara harfiah apa pun di lingkungannya dapat memengaruhinya, terutama perubahan pada masyarakat dan budaya. Sebagian besar negara memiliki undang-undang tentang buku-buku yang jarang diterapkan lagi karena masyarakat telah berubah, tetapi proses pembuatan undang-undang tertinggal. Hukum melawan homoseksualitas adalah contoh saat ini. Atau hukuman mati, yang di sebagian besar negara belum benar-benar diterapkan selama bertahun-tahun atau dekade sebelum dihapus dari buku-buku hukum. Dan bukan karena tidak ada kasus di mana itu bisa diterapkan, tetapi hanya karena hakim tidak menerapkannya meskipun memiliki pilihan.

Faktor-faktor lingkungan ini membuat perkiraan kompleksitas hampir tidak mungkin, karena kita tidak dapat menghitungnya dalam daftar terbatas kecuali kita menggunakan semua-kuantor (mis. "Setiap jenis ..." atau "semua ...")

Tom
sumber
8

Kelengkapan NP, seperti halnya kelas kompleksitas lainnya, ada hubungannya dengan masalah yang mengambil input dengan ukuran yang bervariasi, yang ukurannya ditunjukkan oleh n . Khususnya:

  • Masalahnya adalah NP jika memungkinkan untuk menentukan apakah solusi yang diajukan sebenarnya adalah solusi dengan polinomial runtime di n .

  • Masalah adalah NP-lengkap jika NP dan apalagi setiap masalah NP dapat dikurangi dengan proses pengurangan dengan runtime polinomial di n .

Dalam masalah yang Anda usulkan, yaitu

Mengingat buku hukum ini dan keadaan khusus ini, apakah terdakwa bersalah?

Saya tidak yakin apa yang dimaksudkan dengan n . Sepertinya input di sini adalah "set keadaan" dan nama terdakwa. Hanya yang pertama yang bisa memiliki panjang yang berbeda-beda, tetapi kemudian apa yang kita maksud dengan "seperangkat keadaan"? Apakah kita hanya memberi makan sejumlah fakta sewenang-wenang seperti "terdakwa memiliki kaus kaki ungu" dan "hakim makan sandwich hari ini" atau apa? Selain itu, apakah ada kendala pada keadaan ini, atau bisakah kita memberi makan dalam "keadaan" seperti "tukang cukur Seville mencukur tepat tukang cukur yang tidak mencukur diri mereka sendiri"?

Saya tidak berpikir pertanyaan ini diajukan dengan baik, saya juga tidak melihat cara yang jelas untuk membuatnya dengan baik.

Daniel McLaury
sumber
Sebelum persidangan, sistem peradilan melakukan penyelidikan pendahuluan (tidak yakin apakah itu kata bahasa Inggris yang tepat) di mana semua keadaan yang relevan dikumpulkan. Ukuran dokumen yang mengumpulkan keadaan-keadaan ini bergantung pada kompleksitas kejahatan - untuk kasus-kasus sederhana hanya beberapa lusin halaman dan untuk yang kompleks (misalnya Microsoft antitrust), puluhan ribu halaman atau lebih.
Björn Lindqvist
5

Saya pikir apa yang hilang dalam jawaban yang sangat baik sejauh ini adalah bahwa teori perhitungan mengasumsikan diketahui, pasti, input data, sedangkan undang-undang beroperasi di bidang di mana faktanya biasanya tidak pasti dan kabur. Hukum pidana, misalnya, menyangkut dirinya sendiri dengan "niat" atau "keadaan pikiran" seorang terdakwa, yang tidak pernah bisa diketahui dengan pasti. Pengadilan perceraian harus memutuskan apakah perkawinan telah "dipatahkan". Tidak akan pernah ada algoritma untuk memutuskan pertanyaan itu.

Michael Kay
sumber
0

Sementara beberapa jawaban mengatakan itu tidak dapat diputuskan, saya kira itu bukan untuk apa hukum, karena mereka tidak dapat ditegakkan.

Jika dibatasi dalam beberapa hal yang membuatnya selalu dapat ditentukan, mungkin tidak masuk akal untuk berbicara tentang kerumitan yang sebenarnya. Itu karena input hukum sebagai fungsi umumnya bukan definisi peristiwa dalam hukum, seperti dalam permainan kartu, tetapi bukti bahwa peristiwa itu legal atau tidak.

Mungkin ada banyak bukti sewenang-wenang tentang satu peristiwa. Untuk suatu peristiwa, tidak ada panjang input objektif untuk memungkinkan untuk menentukan kompleksitas. Dan untuk set bukti tertentu, sementara ada panjang input, hukum biasanya tidak menentukan bahwa seseorang harus memiliki kesimpulan yang pasti. Mereka bisa, dan biasanya lebih suka mencoba mengumpulkan lebih banyak bukti bahkan jika jawabannya secara teoritis dapat disimpulkan dengan cara yang sulit. Dan seorang tersangka dapat mengakui sesuatu dengan cara yang membingungkan untuk meningkatkan kompleksitas secara artifisial jika seseorang harus bekerja tanpa bukti.

Akan ada lebih banyak masalah jika kriptografi terlibat. Mereka secara teoritis dapat membalikkan algoritma enkripsi yang kuat jika mereka dapat menghitung untuk waktu yang lama, tetapi mereka dapat merusak kepercayaan diri dari algoritma tanda tangan untuk membuatnya tidak dapat digunakan sebagai bukti pada saat yang sama.

pengguna23013
sumber
0

Anggota juri akhirnya memberikan vonis berdasarkan hukum yang berlaku yang diberikan oleh hakim kepada juri untuk mengikuti dan fakta-fakta yang ditentukan oleh juri menggunakan faktor-faktor dalam instruksi juri. Terutama kredibilitas saksi ... siapa yang harus dipercaya. Tidak dapat direduksi menjadi suatu algoritma.

Tom Whitaker Jr
sumber
Ini tampaknya menjadi upaya yang agak filosofis, yang bertentangan dengan ilmu komputer. Itu tidak salah, tapi mungkin tidak membantu untuk pertanyaan yang diajukan di situs ini .
Raphael
Tergantung pada apakah cs mempertimbangkan kebenaran dasar dari suatu aplikasi dan apakah itu layak atau tidak. Saat ini, diskusi apa pun tanpa menyertakan titik sentuh AI tampaknya tidak biasa. Tapi itu dari uji coba 35+ tahun dan bukan cs guru.
Tom Whitaker Jr
1
Jawaban ini adalah pengingat yang baik tentang sejauh mana teori komputabilitas atau decidability cs dari praktik hukum.
Lulus. Jack
@ TomWhitakerJr Perspektif saya, untuk tujuan menjaga ruang lingkup situs ini, adalah bahwa meskipun menerapkan teknik CS harus diikat oleh pertimbangan etis / filosofis, studi tentang teknik-teknik tersebut tidak. Saya sepenuhnya menyadari bahwa diskusi panjang ada di sana, tetapi saya tidak melihat bagaimana kita dapat membuat situs ini berfungsi dengan baik untuk pertanyaan teknis dan etika / filosofis. Jadi sementara saya sepenuhnya setuju bahwa diskusi seperti bagaimana AI harus digunakan harus diadakan di suatu tempat, saya tidak berpikir situs ini tempat untuk itu.
Raphael