Contoh bagus dari “dua itu mudah, tiga itu sulit” dalam ilmu komputasi

29

Baru-baru ini saya menemukan formulasi dari fenomena-meta : " dua itu mudah, tiga itu sulit " (diucapkan seperti ini oleh Federico Poloni), yang dapat dijelaskan, sebagai berikut:

Ketika masalah tertentu dirumuskan untuk dua entitas, itu relatif mudah untuk diselesaikan; Namun, algoritma untuk formulasi tiga entitas meningkat dalam kesulitan luar biasa, bahkan mungkin membuat solusi tidak layak atau tidak dapat dicapai.

_{(Saya menyambut saran untuk membuat frasa lebih indah, ringkas, dan akurat.)}

Contoh bagus apa dalam berbagai bidang ilmu komputasi (mulai dari aljabar linier murni dan diakhiri dengan fisika komputasi istilah selimut) yang Anda tahu?

linear-algebra computational-physics computational-geometry computational-chemistry Anton Menshov
sumber

2

Kutukan dimensi datang ke pikiran.

Paul

4

grafik 2-warna ( mudah ) versus 3-warna ( NP-hard ), lihat di sini

GoHokies

5

@GoHokies Tolong jangan posting jawaban sebagai komentar.

David Richerby

4

Dari dasar matematika atau latar belakang rekursi, Anda mungkin menemukan fungsi TREE , di mana TREE (2) = 3, dan TREE (3) adalah ... cukup besar. (tidak terbiasa dengan ilmu komputasi, saya tidak yakin ini benar-benar jawaban yang Anda cari, tetapi tampaknya cukup mirip untuk memberikan komentar)

BurnsBA

2

Contoh tandingan: "Jangan pernah melaut dengan dua kronometer; ambil satu atau tiga." Yang mengatakan, ada begitu banyak contoh bagus sehingga tidak ada jawaban yang benar. Pertanyaan ini haruslah wiki komunitas.

David Hammen

35

Salah satu contoh yang muncul di banyak bidang fisika, dan khususnya mekanika klasik dan fisika kuantum, adalah masalah dua tubuh. Masalah dua tubuh di sini berarti tugas menghitung dinamika dua partikel yang berinteraksi, misalnya, berinteraksi dengan gaya gravitasi atau gaya Coulomb. Solusi untuk masalah ini sering dapat ditemukan dalam bentuk tertutup oleh transformasi variabel menjadi pusat massa dan koordinat relatif.

Namun, begitu Anda mempertimbangkan tiga partikel, secara umum tidak ada solusi bentuk tertutup .

Davidhigh
sumber

3

Nitpick bahwa saya yakin Anda tahu, tetapi jawaban Anda tidak menyatakan: Ada solusi bentuk-tertutup untuk masalah 3-tubuh, tetapi hanya untuk beberapa kasus khusus

llama

nitpick yang baik, terima kasih, "secara umum" tidak ada di sini.

davidhigh

Perhatikan bahwa masalah 3-tubuh memang memiliki solusi seri ( sangat lambat konvergen) yang ditemukan oleh Sundman di awal abad ke-20 dan versi yang lebih lemah (yang mengabaikan singularitas di mana tubuh bertabrakan) ditemukan untuk masalah n-tubuh pada tahun 1990.

WorldSEnder

27

Contoh terkenal adalah masalah kepuasan boolean (SAT). 2-SAT tidak rumit untuk diselesaikan dalam waktu polinomial, tetapi 3-SAT adalah NP-lengkap.

Federico Poloni
sumber

3

3-SAT dapat dikurangi menjadi grafik 3-warna, atau sebaliknya

GoHokies

8

@GoHokies saya pikir itu benar untuk setiap masalah np-complete? Atau ada sesuatu yang sangat penting tentang keduanya? Sry jika ini pertanyaan bodoh, pengetahuan saya tentang bidang ini dasar. Tapi beginilah cara saya memahami teorema memasak

findusl

2

@findusl Anda benar sekali. Apa yang membuat 3-SAT dan 3-warna “istimewa” adalah dikotomi 2-vs-3 OP.

GoHokies

26

Dalam satu dan dua dimensi, semua jalan mengarah ke Roma, tetapi tidak dalam tiga dimensi.

Secara khusus, diberi jalan acak (sama-sama cenderung bergerak ke segala arah) pada bilangan bulat dalam satu atau dua dimensi, maka tidak peduli titik awal, dengan probabilitas satu (alias hampir pasti), jalan acak akhirnya akan sampai ke tempat yang ditentukan khusus. point ("Roma").

Namun, untuk tiga dimensi atau lebih, probabilitas untuk sampai ke "Roma" kurang dari satu; dengan probabilitas menurun seiring meningkatnya jumlah dimensi.

Jadi misalnya, jika melakukan simulasi stokastik (Monte Carlo) jalan acak yang dimulai dari "Roma", yang akan berhenti ketika Roma kembali ke, maka dalam satu dan dua dimensi, Anda dapat yakin pada akhirnya membuatnya kembali ke Roma dan menghentikan simulasi - sangat mudah. Dalam tiga dimensi, Anda mungkin tidak akan pernah bisa kembali, sekeras itu.

https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

Untuk memvisualisasikan kasus dua dimensi, orang dapat membayangkan seseorang berjalan secara acak di sekitar kota. Kota ini efektif tanpa batas dan diatur dalam kotak trotoar persegi. Di setiap persimpangan, orang tersebut secara acak memilih salah satu dari empat rute yang mungkin (termasuk yang awalnya ditempuh dari). Secara formal, ini adalah jalan acak pada set semua titik di pesawat dengan koordinat bilangan bulat.

Apakah orang tersebut akan kembali ke titik awal awal perjalanan? Ini adalah padanan 2 dimensi dari masalah level persimpangan yang dibahas di atas. Pada tahun 1921 George Pólya membuktikan bahwa orang tersebut hampir pasti akan berjalan secara 2 dimensi, tetapi untuk 3 dimensi atau lebih tinggi, kemungkinan untuk kembali ke asal berkurang seiring dengan meningkatnya jumlah dimensi. Dalam 3 dimensi, probabilitas berkurang menjadi sekitar 34%

Lihat http://mathworld.wolfram.com/PolyasRandomWalkConstants.html untuk nilai numerik.

Mark L. Stone
sumber

21

Berikut ini satu hal yang dekat dengan hati para kontributor di SciComp.SE:

The Navier-Stokes keberadaan dan kelancaran masalah

Versi tiga dimensi tentu saja merupakan masalah terbuka yang terkenal dan menjadi subjek Hadiah jutaan dolar Clay. Tetapi versi dua dimensi telah dipecahkan sejak lama, dengan jawaban yang meyakinkan. Terry Tao mencatat bahwa solusinya pada dasarnya kembali ke tesis Leray pada tahun 1933!

Mengapa masalah tiga dimensi jauh lebih sulit untuk dipecahkan? Respon standar, tangan-bergelombang adalah bahwa turbulensi menjadi jauh lebih tidak stabil dalam tiga dimensi daripada dua. Untuk jawaban yang lebih matematis, lihat pernyataan masalah resmi Charles Fefferman di Clay Institute atau penjelasan bagus Terry Tao tentang strategi bukti yang mungkin .

Richard Zhang
sumber

20

Dalam teori pilihan sosial, merancang skema pemilihan dengan dua kandidat itu mudah (aturan mayoritas), tetapi merancang skema pemilihan dengan tiga kandidat atau lebih tentu melibatkan melibatkan pertukaran antara berbagai kondisi yang masuk akal. ( Teorema ketidakmungkinan Arrow ).

ajd
sumber

11

$A_1$ $A_2$

U_{1}^{T} A_{1} V = Σ_{1}, U_{2}^{T} A_{2} V = Σ_{2}

$U_1^T A_1 V = \Sigma_1,\quad U_2^TA_2V=\Sigma_2$

Namun, ketika pengurangan simultan dari tiga matriks ke bentuk kanonik (kondisi yang lebih lemah dibandingkan dengan yang di atas) diperlukan:

Q^{T} A_{1} Z = \tilde{A_{1}}, Q^{T} A_{2} Z = \tilde{A_{2}}, Q^{T} A_{3} Z = \tilde{A_{3}}

$Q^T A_1 Z = \tilde{A_1},\quad Q^T A_2 Z = \tilde{A_2},\quad Q^T A_3 Z = \tilde{A_3}$

(A_{1} + λ A_{2} + λ^{2} A_{3}) x = 0

$(A_1+\lambda A_2+\lambda^2 A_3)x=0$

Sumber: CF van Loan, "Kuliah 6: Dekomposisi nilai singular umum tingkat tinggi," CIME-EMS Summer School, Cetraro, Italia, Juni 2015.

Anton Menshov
sumber

U_{1}^{T}

$U_1^T$

U_{2}^{T}

$U_2^T$

V^{- 1}

$V^{-1}$

1

Σ

$\Sigma$

9

Ada banyak contoh dalam komputasi kuantum, meskipun saya sudah keluar dari ini untuk sementara waktu dan jadi tidak ingat banyak. Satu yang utama adalah bahwa keterikatan bipartit (keterikatan antara dua sistem) relatif mudah sedangkan keterikatan di antara tiga atau lebih sistem adalah kekacauan yang tidak terpecahkan dengan kemungkinan seratus makalah yang ditulis pada topik.

$\max\left(u_a v_b w_c T^{abc} / \left\lVert u \right\rVert \left\lVert v \right\rVert \left\lVert w \right\rVert \right)$

Makalah ini tampaknya relevan, meskipun saya belum membacanya: Sebagian besar masalah tensor NP-hard

Dan Stahlke
sumber

2

Saya merasa seperti masalah sebenarnya yang Anda dapatkan adalah bahwa dekomposisi peringkat tensor mudah untuk tensor orde-1 (vektor) dan orde-2 tensor (matriks), tetapi NP-hard untuk sisanya

Richard Zhang

Itu bagian dari itu, tetapi bahkan jika Anda memiliki cara menguraikan mereka masih ada masalah pengelompokan / klasifikasi. Untuk kesatuan kesatuan lokal tidak masalah, jadi yang tersisa dalam kasus urutan-2 adalah daftar nilai singular (SVD disebut dekomposisi Schmidt dalam konteks ini). Untuk pesanan yang lebih tinggi ada banyak kebun binatang kemungkinan. Pertanyaan-pertanyaan seperti negara mana yang dapat ditransformasikan menjadi negara-negara lain melalui operasi lokal berakhir sangat sulit (dari sudut pandang teoritis, tidak harus komputasi).

Dan Stahlke

5

Pembelahan sudut dengan penggaris lurus dan kompas adalah sederhana, pembagian tiga sudut pada umumnya tidak mungkin.

Davidhigh
sumber

4

Ketik inferensi untuk tipe Peringkat-n . Ketik inferensi untuk Peringkat-2 tidak terlalu sulit, tetapi inferensi tipe untuk Peringkat-3 atau di atas tidak dapat ditentukan.

André Popovitch
sumber

4

Berikut ini salah satu dari optimasi: algoritma Alternating Direction of Multipliers (ADMM).

Diberikan fungsi objektif yang tidak terpisahkan dan cembung dari dua variabel (variabel itu sendiri bisa menjadi vektor) dan kendala linear yang menyertai dua variabel:

min f_{1} (x_{1}) + f_{2} (x_{2})

$\min f_1(x_1) + f_2(x_2)$

s . t . A_{1} x_{1} + A_{2} x_{2} = b

$s.t. \; A_1 x_1 + A_2 x_2 = b$

L_{ρ} (x_{1}, x_{2}, λ) = f_{1} (x_{1}) + f_{2} (x_{2}) + λ^{T} (A_{1} x_{1} + A_{2} x_{2} - b) + \frac{ρ}{2} | | A_{1} x_{1} + A_{2} x_{2} - b | |_{2}^{2}

$L_{\rho}(x_1, x_2, \lambda) = f_1(x_1) + f_2(x_2) + \lambda^T (A_1 x_1 + A_2 x_2 - b) + \frac{\rho}{2}|| A_1 x_1 + A_2 x_2 - b ||_2^2$

$L_{\rho}(x_1, x_2, \lambda)$ $x_1$ $x_2, \lambda$ $L_{\rho}(x_1, x_2, \lambda)$ $x_2$ $x_1, \lambda$ $\lambda$ . Siklus ini berlangsung hingga kriteria berhenti tercapai.

(Catatan: beberapa peneliti seperti Eckstein membuang pandangan pemisahan Gauss-Siedel yang mendukung operator proksimal, misalnya lihat http://rutcor.rutgers.edu/pub/rrr/reports2012/32_2012.pdf )

Untuk masalah cembung, algoritma ini telah terbukti konvergen - untuk dua set variabel. Ini bukan kasus untuk tiga variabel. Misalnya masalah optimasi

min f_{1} (x_{1}) + f_{2} (x_{2}) + f_{3} (x_{3})

$\min f_1(x_1) + f_2(x_2) + f_3(x_3)$

s . t . A_{1} x_{1} + A_{2} x_{2} + A_{3} x_{3} = b

$s.t. \; A_1 x_1 + A_2 x_2 + A_3x_3 = b$

$f$ $x_i$ $\lambda$

https://web.stanford.edu/~yyye/ADMM-final.pdf

Nathaniel Kroeger
sumber

3

Melipat selembar kertas menjadi dua tanpa alat itu mudah. Melipatnya menjadi tiga adalah sulit.

Memfaktorkan polinomial dengan dua akar itu mudah. Anjak polinomial dengan tiga akar secara signifikan lebih rumit.

Lupus Arcanist
sumber

3

Contoh pertama Anda tidak sesuai dengan semangat kutipan. Idenya adalah bahwa karena semakin tinggi melewati dua itu lebih sulit, namun dengan melipat kertas, keempat hanya semudah setengah. Kutipan di sini adalah "Bahkan lebih mudah daripada aneh" Saya pikir yang kedua adalah baik - dan terima kasih untuk mencoba menyederhanakannya dengan kertas!

Bill K

3

$f(x,y) = 0$ $f$

Perbedaan ini memiliki beberapa implikasi:

Pada derajat 2 terdapat algoritma untuk menemukan semua titik rasional (solusi dalam bilangan rasional), pada derajat 3 tidak ada algoritma yang diketahui.
$\sqrt{f(x)}$ $f$ $f$
Masalah logaritma diskrit dapat ditelusuri pada kurva derajat 2, karenanya tidak cocok untuk aplikasi kriptografi, sedangkan kekerasan yang diasumsikan dari masalah yang sama pada kurva eliptik adalah pada dasar beberapa cryptosystems kunci publik yang paling populer.

doetoe
sumber

1

The TREEfungsi.

Kita dapat menghitung TREE(2) = 3, tetapi TREE(3)tidak dapat dihitung dalam masa hidup semesta, kita hanya tahu bahwa itu terbatas.

justhalf
sumber

TREE(3)

n

$n$

n

$n$

Benar, maaf atas kesalahannya. Memperbaiki pernyataan saya. Solomonoff terima kasih!

justhalf

1

Video numberphile terkait tentang Tree (3): youtube.com/watch?v=3P6DWAwwViU

Novice C

1

Dalam ruang dua dimensi, Anda dapat memperkenalkan struktur kompleks, yang dapat digunakan untuk menyelesaikan banyak masalah secara elegan (misalnya masalah aliran potensial ), tetapi tidak ada analog dalam 3 dimensi.

Patrick Sanan
sumber

0

Dalam fisika banyak-tubuh kuantum, kita mempelajari berbagai kisi-kisi n berputar dalam kerangka model yang berbeda (misalnya model Heisenberg, model Bose-Hubbard, model Ising, ...). Anda tentu saja memiliki metode numerik yang berbeda untuk mempelajarinya (DMRG, diagonalisasi yang tepat, jaringan saraf, ...) dan salah satu alasan kami mencoba mengembangkan metode yang berbeda adalah karena Anda tidak dapat menyelesaikan model ini ketika n menjadi terlalu "tinggi" , dan tentu saja lebih buruk jika Anda belajar di dimensi yang lebih tinggi. Misalnya, untuk Model Ising, diagonisasi yang tepat bekerja dengan baik dalam 1d untuk n tidak lebih tinggi dari 20. Jadi, untuk n yang lebih tinggi, Anda mencoba metode lain: DMRG. Tetapi yang terakhir ini memang bekerja dengan baik untuk n yang lebih tinggi (seperti n = 70 tetapi tidak baik untuk n yang lebih tinggi). Sekali lagi, Anda ingin metode lain untuk jaringan saraf yang lebih tinggi (yaitu kecerdasan buatan). Dan di samping dengan jaringan saraf, Anda dapat mempelajari "lebih mudah" (yaitu dengan relatif lebih tinggi n) model-model ini dalam dimensi yang lebih tinggi (tetapi untuk dimensi = 3 dan n kecil, misalnya, masih membutuhkan banyak jam (beberapa hari) untuk mendapatkan keadaan dasar atau diamati Anda inginkan ...). Bref, ketika n menjadi "terlalu tinggi" untuk metode numerik Anda (tetapi juga kapasitas komputer Anda), Anda perlu melakukan metode baru (dan jika Anda bisa, gunakan komputer super) dan itu adalah masalah yang sama dengan dimensi Anda Sistem tetapi lebih buruk tentu saja karena Anda dengan cepat terjebak (dimensi = 4 sulit diperoleh kecuali jika Anda menunggu banyak waktu ...). masih membutuhkan banyak jam (beberapa hari) untuk mendapatkan kondisi dasar atau yang dapat diamati yang Anda inginkan ...). Bref, ketika n menjadi "terlalu tinggi" untuk metode numerik Anda (tetapi juga kapasitas komputer Anda), Anda perlu melakukan metode baru (dan jika Anda bisa, gunakan komputer super) dan itu adalah masalah yang sama dengan dimensi Anda Sistem tetapi lebih buruk tentu saja karena Anda dengan cepat terjebak (dimensi = 4 sulit diperoleh kecuali jika Anda menunggu banyak waktu ...). masih membutuhkan banyak jam (beberapa hari) untuk mendapatkan kondisi dasar atau yang dapat diamati yang Anda inginkan ...). Bref, ketika n menjadi "terlalu tinggi" untuk metode numerik Anda (tetapi juga kapasitas komputer Anda), Anda perlu melakukan metode baru (dan jika Anda bisa, gunakan komputer super) dan itu adalah masalah yang sama dengan dimensi Anda Sistem tetapi lebih buruk tentu saja karena Anda dengan cepat terjebak (dimensi = 4 sulit diperoleh kecuali jika Anda menunggu banyak waktu ...).
Tentu saja, di sini, ini lebih banyak informasi tambahan untuk pertanyaan Anda karena sebenarnya, dalam fisika kuantum banyak-tubuh, n = 3 tidak tinggi (tetapi jika Anda mengambil kisi yang merupakan hypercube, Anda tidak dapat mengambil n = 3 dari Tentu saja (karena kondisi)).

Albert B.
sumber

-3

Dunia nyata:

Automation% - mis. Mudah untuk mengotomatisasi sesuatu dalam 30% atau 50% atau 80% sementara itu sulit untuk pergi misalnya di atas 95% dan sangat sulit atau bahkan hampir tidak mungkin mencapai 100%.

Joelty
sumber

2

Bisakah Anda memberikan referensi untuk klaim Anda?

nicoguaro

Saya tidak bisa, tetapi perhatikan misalnya mobil self-driving. Mempelajari mobil untuk mengemudi lurus dan mengendalikan kecepatan mungkin lebih mudah daripada belajar mengemudi seperti orang normal. Proses yang lebih kompleks adalah, maka lebih banyak kasus perbatasan muncul ketika Anda ingin membuatnya sepenuhnya otomatis

Joelty

Lalu, saya pikir pertanyaan Anda tidak sesuai untuk situs ini.

nicoguaro

Contoh bagus dari “dua itu mudah, tiga itu sulit” dalam ilmu komputasi

Jawaban: