Hasil menarik dalam TCS yang mudah dijelaskan kepada programmer tanpa latar belakang teknis

13

Misalkan Anda bertemu dengan programmer yang telah mengambil beberapa program pemrograman profesional (/ saya pikir sendiri) tetapi tidak belajar matematika tingkat universitas.

Untuk menunjukkan kepada mereka keindahan TCS, saya ingin mengumpulkan beberapa hasil bagus / pertanyaan terbuka yang berasal dari TCS yang dapat dengan mudah dijelaskan.

Kandidat yang baik untuk tujuan ini (IMHO) akan menunjukkan bahwa masalah penghentian tidak dapat diputuskan. Lain akan menunjukkan batas bawah pada waktu berjalan penyortiran berbasis perbandingan (meskipun itu sedikit mendorongnya dari apa yang saya harapkan mereka mengerti).

Saya juga dapat menggunakan ide-ide dari Jelaskan masalah P = NP hingga 10 tahun , dengan asumsi beberapa dari mereka tidak terbiasa dengannya.

Jadi, pertanyaannya adalah:

(0. Cantik)

  1. Dapat dijelaskan dengan (paling banyak) matematika sekolah menengah.
  2. (lebih disukai) tidak cukup sepele untuk ditampilkan dalam kursus pemrograman profesional (untuk C ++ / Java / Web / dll.).
soft-question big-list big-picture teaching BPR
sumber
Bukankah ini sepenuhnya berdasarkan opini?
David Richerby
6
Saya pikir itu pertanyaan yang bagus. Pertanyaan serupa dan bermanfaat pada mathoverflow: mathoverflow.net/questions/47214/… . mathoverflow.net/questions/56547/aplikasi-dari-mathematics .
usul
1
juga agak mirip dengan "deskripsi meja makan TCS" . Saya favorit saya adalah adanya fungsi keras yang dibuktikan oleh Shannon tetapi hampir tidak ada bukti konstruktif dari setiap fungsi keras tertentu setelah lebih dari 1/2 abad ....
vzn
1
Keberadaan quines selalu menyenangkan untuk disebutkan kepada programmer.
Denis
2
mungkin itu komunitas wiki?
Suresh Venkat

Jawaban:

9

Selain masalah penghentian, saya sarankan mendiskusikan:

Teorema Padi. Beberapa penjelasan di Wikipedia sedikit berat, tetapi umumnya bukan teorema atau bukti yang sulit dipahami selain itu; ia memiliki banyak relevansi dengan konsep dunia nyata seperti perangkat lunak anti-virus. Buktinya hampir sama terlibatnya dengan bukti masalah penghentian (dan sebenarnya tergantung pada ketidakpastian masalah penghentian). Pada dasarnya, cukup pahami bahwa "fungsi yang dapat dihitung" adalah mesin atau program komputer Turing.

Philip White
sumber
4
Saya tidak berpikir kekerasan anjak diketahui menyiratkan keamanan RSA.
Sasho Nikolov
1
Itu adalah kesenjangan yang signifikan dalam pengetahuan saya tentang kripto. Terima kasih telah menunjukkannya; Saya mengedit jawaban saya.
Philip White
1
Jika Anda tertarik, Anda dapat melihat ini: crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf . Namun, contoh Anda bagus, meskipun detailnya salah. Untuk Diffie-Hellman, kesetaraan dengan log diskrit dikenal untuk banyak kelompok siklik, bisa dibilang termasuk yang digunakan dalam aplikasi praktis: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3339 . Juga, Diffie-Hellman sebenarnya lebih mudah dijelaskan daripada RSA, IMO
Sasho Nikolov
5

Saya berpikir bahwa - secara independen dari pertanyaan P vs NP - teorema Cook-Levin (dan gagasan terkait kelengkapan NP) adalah kandidat lain yang sangat baik; jika Anda memiliki solver (efisien) untuk SAT maka Anda memiliki solver (efisien) untuk setiap masalah dalam NP .... dan Anda dapat berakhir dengan sesuatu yang mencengangkan, setidaknya untuk saya:

  • Sebuahx12+bx2+c=0
  • memecahkan Sudoku;
  • menemukan jalur Hamiltonian dalam grafik;
  • memecahkan contoh jumlah subset;
  • dan banyak masalah (kehidupan nyata) lainnya ...

dalam beberapa hal "masalah setara"; jadi jika bos Anda meminta Anda untuk membuat program untuk mengemas kotak ke dalam wadah ... Anda dapat memberinya pemecah Minesweeper ... :-)

Marzio De Biasi
sumber
4

Contoh yang menyenangkan dan menghibur adalah ketidakpastian masalah ubin ubin Wang. Hasilnya mengikuti langsung dari ketidakpastian masalah Menghentikan dengan simulasi sederhana mesin Turing menggunakan ubin Wang. Menariknya, ketidakpastian masalah ubin untuk ubin Wang menyebabkan hasil yang indah bahwa ada set ubin yang ubin pesawat hanya aperiodicaly.

Wang menduga bahwa setiap ubin mengatur bahwa ubin pesawat harus memiliki ubin berkala. Oleh karena itu, dugaan tersebut menyiratkan bahwa masalah ubin dapat diputuskan. Kemudian, Burger membuktikan ketidakpastian masalah ubin yang menyiratkan adanya set ubin yang ubin pesawat hanya aperiodicaly.

NPNP

Mohammad Al-Turkistany
sumber
3

favorit dikumpulkan dari sini & di tempat lain

vzn
sumber
2
juga algoritma lain yang sangat penting dengan beberapa sudut TCS yang dalam: Pagerank
vzn