Contoh pedantry di TCS

Larry Wasserman memiliki posting baru-baru ini di mana ia berbicara tentang "polisi p-value". Dia membuat poin yang menarik (semua penekanan pada saya) (premis miring yang saya tambahkan, dan jawabannya di bawah):

Keluhan yang paling umum adalah bahwa fisikawan dan jurnalis menjelaskan arti nilai-p secara tidak benar. Misalnya, jika nilai-p adalah 0,000001 maka kita akan melihat pernyataan seperti "ada kepercayaan 99,9999% bahwa sinyal itu nyata." sebagai atau lebih ekstrim adalah 0,000001.

Cukup adil. Tetapi apakah itu benar-benar penting? Gambaran besarnya adalah: bukti pengaruhnya sangat besar. Apakah benar-benar penting jika kata-katanya sedikit menyesatkan? Saya pikir kita memperkuat citra kita sebagai pengedarnya jika kita mengeluh tentang ini.

Yang membuat saya berpikir -

Apakah ada contoh pedantry yang bagus di TCS? Contoh seperti itu akan terdiri dari

• Klaim yang umumnya dibuat di media populer
• Koreksi standar yang dilakukan orang-orang
• "Gambaran besar" yang benar yang diklaim tidak ditangkap bahkan saat tidak tepat.

di mana klaim secara matematis salah tetapi "benar secara moral" dan koreksi secara teknis benar tetapi tidak mengubah pemahaman intuitif.

Untuk memimpin, contoh saya adalah:

• Klaim - Masalah NP-lengkap membutuhkan waktu eksponensial untuk dipecahkan
• Koreksi - Tidak sebenarnya kita tidak tahu apakah bisa diselesaikan dalam waktu polinomial
• Gambaran besar - Masalah NP-complete HARD

Perhatian: Saya tahu ada banyak di forum ini yang kepalanya akan meledak pada gagasan klaim yang salah tetapi "benar secara moral" :). Ingatlah bahwa ini adalah pernyataan yang ditargetkan untuk publik (di mana beberapa tingkat lisensi dapat diizinkan), daripada pernyataan yang dibuat dalam makalah penelitian.

Hm, alangkah sulitnya memikirkan contoh-contoh klaim tentang TCS yang membuatnya menjadi berita populer.

Satu hal yang saya lihat kadang-kadang adalah klaim bahwa anjak piutang adalah NP-hard, ketika menjelaskan kriptografi. Ini terkait dengan kesalahan yang tidak berbahaya dalam mengklaim bahwa komputer kuantum dapat menyelesaikan masalah sulit NP, tetapi terbatas pada konteks kriptografi, ini adalah kesalahan yang relatif ringan. Intinya adalah kita (pengguna kriptografi) tampaknya percaya bahwa tidak ada algoritma yang efisien untuk menyelesaikan masalah. Dugaan khusus yang kami gunakan untuk membenarkan pernyataan ini adalah selain itu intinya.

• klaim oleh pers: tentang hal-hal yang tumbuh "secara eksponensial" yaitu klaim O (k ^ n)

• sebenarnya benar: sering, kekuatan konstan O (n ^ k)

• gambaran besar: itu tumbuh cukup cepat, oke

• Klaim melalui pers: Algoritma waktu polinomial pertama untuk masalah praktis yang penting tentu akan mengubah hidup kita, akan menjadi hal terbaik berikutnya setelah memotong roti, dll.

Sebagai contoh, ambil artikel pers tentang algoritma ellipsoid sejak ditemukan (kisah hebat tentang ini: http://www.springerlink.com/content/vh32532p5048062u/ ). Pers mengklaim bahwa penemuan matematis baru yang hebat ini akan memengaruhi kehidupan semua orang, menyelesaikan TSP (yang mereka temukan sangat ironis mengingat betapa sedikitnya salesman keliling di Uni Soviet!), Mengubah kripto menjadi terbalik, dll.

Lalu ada AKS, yang dalam beberapa laporan bahkan tersirat untuk menyelesaikan anjak piutang .. atau setidaknya menjadi inovasi yang mengubah industri.

Saya yakin ada banyak lagi contoh.

• Sebenarnya benar: Waktu polinomial bukan berarti praktis! Contoh kasus: algoritma ellipsoid, pengambilan sampel dari badan cembung dimensi tinggi. Waktu eksponensial terburuk tidak berarti tidak praktis. Contoh kasus: algoritma simpleks. Ketika algoritma baru hanyalah algoritma polytime deterministik pertama untuk suatu masalah, ini bahkan memiliki relevansi yang lebih rendah untuk dipraktikkan.

• $\log^5 n$

Pers populer sering memberi kesan bahwa alasan utama, jika bukan satu-satunya, bahwa komputer berhasil dalam tugas yang semakin banyak (mengalahkan Kasparov di catur, mengalahkan Jennings di Jeopardy, dll.) Adalah peningkatan daya pemrosesan mentah. Kemajuan algoritma biasanya tidak diberi banyak pujian.

Namun, saya ambivalen tentang apakah bersikeras bahwa kemajuan algoritmik diberikan bobot lebih adalah "kesedihan." Di satu sisi, saya berpikir bahwa kita yang lebih cenderung secara teoritis kadang-kadang dapat melebih-lebihkan pentingnya kemajuan algoritmik dan hanya dengan enggan mengakui pentingnya peningkatan daya pemrosesan. Di sisi lain, saya pikir masyarakat harus lebih diberi informasi tentang peran kemajuan teoretis dalam memecahkan masalah praktis.

Scott Aaronson, sementara otoritas terkemuka, tampaknya secara teratur mengambil media untuk tugas untuk tidak memotong rambut secara akurat. misalnya kolomnya baru-baru ini di artikel NYT "Komputasi Quantum Menjanjikan Wawasan Baru, Bukan Hanya Supermachines" [cetak miring ditambahkan]

Berjuang untuk menyemai matematika itu menjadi metafora ramah-koran, penulis paling populer menggambarkan komputer kuantum sebagai mesin ajaib yang dapat memproses setiap jawaban yang mungkin secara paralel, daripada mencoba mereka satu per satu. Seharusnya, itu bisa melakukan itu karena, tidak seperti komputer saat ini yang memanipulasi bit, komputer kuantum akan memanipulasi bit kuantum, atau qubit, yang dapat berupa 0 dan 1 secara bersamaan.

Tapi itu cara kasar untuk memvisualisasikan apa yang dilakukan komputer kuantum, dan melewatkan bagian terpenting dari cerita. Saat Anda mengukur output komputer kuantum, Anda hanya melihat satu jawaban acak - bukan daftar semua jawaban yang mungkin. Tentu saja, jika Anda hanya menginginkan jawaban acak, Anda bisa memilihnya sendiri, dengan lebih sedikit kesulitan.

namun metafora jawaban pemrosesan komputer kuantum secara paralel tersebar luas & penyederhanaan konseptual yang wajar dari komputasi QM, dan dirujuk dalam banyak buku teks komputasi QM. mungkin ada contoh lain dari teori / komputasi QM.

ada ketegangan alami dalam TCS dan penelitian teoretis lainnya dalam berkomunikasi dengan publik / media karena kadang-kadang cenderung menekankan perbedaan / konsep penting sebagai bagian dari pelatihan keras yang tidak dikenal atau penting bagi orang awam. dengan kata lain dalam banyak kasus, teori penelitian bekerja melawan berbagai penyederhanaan "gambaran besar" konseptual yang sah bagi orang awam.