Apakah ada Hukum Konservasi dalam Teori Kompleksitas?

Mari saya mulai dengan beberapa contoh. Mengapa begitu sepele untuk menunjukkan CVP dalam P tetapi begitu sulit untuk menunjukkan LP dalam P; sementara keduanya adalah masalah P-complete.

Atau anggap primality. Lebih mudah untuk menunjukkan komposit dalam NP daripada bilangan prima dalam NP (yang membutuhkan Pratt) dan akhirnya dalam P. Mengapa ia harus menampilkan asimetri ini sama sekali?

Saya tahu Hilbert, perlu kreativitas, buktinya ada di NP dll. Tapi itu tidak menghentikan saya dari perasaan mual bahwa ada lebih dari ini daripada memenuhi mata.

Apakah ada gagasan "pekerjaan" yang dapat diukur dan apakah ada "hukum konservasi" dalam teori kompleksitas? Itu menunjukkan, misalnya, bahwa meskipun CVP dan LP keduanya P-lengkap, mereka menyembunyikan kerumitan mereka di "tempat yang berbeda" - satu dalam pengurangan (Apakah CVP sederhana karena semua pekerjaan dilakukan dalam pengurangan?) Dan lainnya dalam kemampuan mengekspresikan bahasa.

Adakah yang lain juga mual dan dengan beberapa wawasan? Atau apakah kita mengangkat bahu dan berkata / menerima bahwa ini adalah sifat perhitungan?

Ini adalah pertanyaan pertama saya ke forum: semoga saja.

Sunting: CVP adalah Masalah Nilai Sirkuit dan LP adalah Pemrograman Linier. Terima kasih Sadeq, untuk menunjukkan kebingungan.

Ini adalah pertanyaan yang telah berulang kali terlintas di pikiran saya.

Saya pikir satu tempat untuk melihat adalah teori informasi. Ini spekulasi saya. Diberi masalah mungkin kita bisa memberikan semacam nilai entropi ke informasi yang diberikan sebagai input dan informasi yang diterima dari algoritma. Jika kita bisa melakukan itu, maka akan ada sejumlah minimum perolehan informasi yang dibutuhkan oleh suatu algoritma untuk menyelesaikan masalah itu.

Ada satu hal terkait yang ingin saya cari tahu. Dalam beberapa masalah NP-lengkap Anda dapat menemukan versi dibatasi di P; dengan jalur Hamilton jika Anda menentukan bahwa grafik adalah DAG maka ada algoritma p-time untuk menyelesaikannya. Dengan masalah lain seperti TSP, seringkali ada algoritma p-time yang akan mendekati optimal. Menurut saya, untuk algoritma p-time terbatas, harus ada beberapa hubungan proporsional antara informasi tambahan yang diasumsikan dan pengurangan kompleksitas run-time. Dalam kasus TSP kami tidak mengasumsikan informasi tambahan, kami santai ketepatan, yang saya harapkan memiliki efek yang sama pada segala jenis informasi algoritmik yang didapat.

Catatan tentang Hukum Konservasi

Pada awal 1900-an ada sedikit ahli matematika Jerman-Amerika bernama Emily Noether. Antara lain ia digambarkan oleh Einstein dan Hilbert sebagai wanita yang paling penting dalam sejarah matematika. Pada tahun 1915 ia menerbitkan apa yang sekarang dikenal sebagai Teorema Pertama Noether . Teorema ini tentang hukum fisik konservasi, dan mengatakan bahwa semua hukum konservasi memiliki simetri diferensial yang sesuai dalam sistem fisik. Konservasi Momentum Sudut berasal dari simetri rotasi dalam ruang, Konservasi Momentum Linier adalah terjemahan dalam ruang, Konservasi Energi adalah terjemahan dalam waktu. Mengingat bahwa, agar ada hukum pelestarian kompleksitas dalam arti formal, perlu ada beberapa simetri diferensial yang sesuai dalam fungsi Langragian.

Saya pikir alasannya ada dalam sistem logis yang kami gunakan. Setiap sistem formal memiliki seperangkat aksioma , dan seperangkat aturan inferensi .

Suatu pembuktian dalam sistem formal hanyalah urutan formula sehingga setiap formula dalam urutan tersebut adalah aksioma atau diperoleh dari formula sebelumnya dalam urutan tersebut dengan menerapkan aturan inferensi. Teorema sistem formal hanyalah formula terakhir sebagai bukti.

Panjang bukti teorema, dengan asumsi itu dapat ditentukan dalam sistem logis, sangat bergantung pada set aksioma dan aturan inferensi .

Misalnya, pertimbangkan logika proposisional, yang di dalamnya terdapat beberapa penokohan: Frege (1879), Nicod (1917), dan Mendelson (1979). (Lihat survei singkat ini untuk info lebih lanjut.)

$\varphi \to \varphi$

Masalah ini disebut kompleksitas bukti . Mengutip Beame & Pitassi :

Salah satu pertanyaan paling mendasar dari logika adalah sebagai berikut: Diberikan pernyataan yang benar secara universal (tautologi) berapa panjang bukti tersingkat dari pernyataan dalam beberapa sistem bukti aksiomatik standar? Versi logika proposisional dari pertanyaan ini sangat penting dalam ilmu komputer untuk membuktikan teorema dan teori kompleksitas. Pertanyaan algoritmik terkait yang penting adalah: Apakah ada algoritma yang efisien yang akan menghasilkan bukti tautologi? Apakah ada algoritma yang efisien untuk menghasilkan bukti terpendek dari setiap tautologi? Pertanyaan-pertanyaan tentang pembuktian teorema dan kompleksitas mengilhami makalah seminal Cook tentang kelengkapan NP yang terutama berjudul “Kompleksitas prosedur pembuktian teorema” dan bahkan direnungkan sebelumnya oleh Gödel dalam suratnya yang sekarang terkenal kepada von Neumann.

Saya memikirkan pertanyaan yang sama beberapa hari yang lalu, ketika saya memutar ulang beberapa Feynman Lectures on Physics, dan datang ke pelajaran 4 tentang konservasi energi. Dalam ceramah Feynman menggunakan contoh mesin sederhana yang (melalui beberapa sistem tuas atau katrol atau apa pun) menurunkan bobot satu unit dengan jarak x tertentu, dan menggunakannya untuk mengangkat bobot kedua 3 unit. Seberapa tinggi berat badan bisa diangkat? Feynman membuat pengamatan bahwa jika mesin itu reversibel, maka kita tidak perlu tahu apa-apa tentang mekanisme mesin - kita dapat memperlakukannya seperti kotak hitam - dan itu akan selalu mengangkat bobot dengan jarak maksimum yang dimungkinkan ( x / 3 dalam hal ini).

Apakah ini memiliki analog dalam perhitungan? Gagasan komputasi reversibel mengingatkan karya Landauer dan Bennett, tapi saya tidak yakin ini adalah arti istilah yang kami minati. Secara intuitif, jika kita memiliki algoritma untuk beberapa masalah yang optimal, maka tidak ada "pekerjaan" yang sia-sia yang dilakukan dengan mengaduk bit; sementara pendekatan brute-force untuk masalah yang sama akan membuang siklus CPU kiri dan kanan. Namun, saya membayangkan orang dapat membangun sirkuit yang dapat dibalik secara fisik untuk kedua algoritma tersebut.

Saya pikir langkah pertama dalam mendekati undang-undang konservasi untuk kompleksitas komputasi adalah untuk mengetahui dengan tepat apa yang harus dilestarikan. Ruang dan waktu adalah masing-masing metrik penting, tetapi jelas dari keberadaan pertukaran ruang / waktu bahwa tidak satu pun dari keduanya dengan sendirinya akan memadai sebagai ukuran berapa banyak "pekerjaan" yang dilakukan oleh suatu algoritma. Ada metrik lain seperti pembalikan kepala TM atau perlintasan sel pita yang telah digunakan. Tak satu pun dari ini benar-benar dekat dengan intuisi kita tentang jumlah "pekerjaan" yang diperlukan untuk melakukan perhitungan.

Sisi lain dari masalah adalah mencari tahu apa pekerjaan itu dikonversi menjadi. Setelah Anda mendapatkan output dari suatu program, apa sebenarnya yang telah Anda peroleh?

Beberapa pengamatan menunjukkan keberadaan hukum konservasi:

$<_p$$P\ne NP$

$P=\{L| L<_p HornSAT \}$

$NP=\{L| L<_p 3SAT \}$

$CoNP=\{L| \bar L<_p 3SAT \}$

$NPC=\{L| L<_p 3SAT, 3SAT<_p L \}$

$PC=\{L| L<_p HornSAT, HornSAT<_p L \}$

$P$$P=\{L| L<_p HornSAT, \bar L <_p HornSAT \}$$P$$NP$$P=NP$

Tao menyarankan keberadaan hukum kekekalan dalam matematika: "untuk membuktikan hasil yang tidak sepele, beberapa kerja keras harus dilakukan di suatu tempat".

Dia berpendapat bahwa kesulitan dari beberapa bukti matematika menunjukkan ikatan yang lebih rendah dengan jumlah upaya yang dibutuhkan oleh proses pembuktian teorema.