Bagaimana Anda mendapatkan "Intuisi Fisik" untuk hasil dalam TCS?

Saya minta maaf jika pertanyaan ini agak kabur, tetapi saya ingin tahu bagaimana para peneliti yang sukses mendapatkan "perasaan" untuk hasil di TCS.

Misalnya, aljabar linier dapat dipahami secara geometris, atau dalam hal interpretasi fisiknya (vektor eigen dapat dianggap sebagai "titik stabil" dalam suatu sistem), dll. Juga intuitif bahwa terdapat protokol IP untuk TQBF (seperti IP protokol dapat divisualisasikan sebagai semacam "permainan" antara dua entitas dengan kekuatan komputasi yang sangat berbeda). Namun, saya menemukan bahwa banyak hasil, bahkan yang sangat mendasar di TCS tidak memiliki intuisi sederhana (MA AM). Lebih buruk lagi, kadang-kadang, intuisi yang tidak dimurnikan menjadi sangat waspada (2-SAT dalam P sementara 3-SAT tidak diyakini berada dalam P (pada kenyataannya, adalah NP-lengkap)). Apakah ada "prinsip umum" untuk mengembangkan intuisi di TCS?$\subseteq$

Seperti banyak bidang ilmiah, diperlukan waktu bertahun-tahun untuk membangun intuisi, tetapi hanya butuh satu ide baru untuk meruntuhkan intuisi itu (dan mudah-mudahan sesuatu yang bagus dapat dibangun kembali di tempatnya).

Ada beberapa latihan dasar yang dapat Anda gunakan untuk mencoba membangun intuisi untuk beberapa makalah yang Anda baca dan sepertinya tidak bisa menembus. Inilah yang masih saya lakukan dari waktu ke waktu. Mulailah dengan bukti yang tidak Anda mengerti tetapi benar-benar ingin, yang sangat panjang. Saat Anda membaca setiap paragraf dari buktinya, cobalah untuk menulis kalimat dengan kata - kata Anda sendiri tentang apa yang Anda pikirkan paragraf katakan, di margin. Semoga buktinya ditulis dengan cukup baik sehingga ada "bagian" yang terdefinisi dengan baik menjadi buktinya ("lakukan X, lalu tentukan fungsi baru f, lalu terapkan X ke f, ..."). Jika tidak, maka dari kalimat Anda, pisahkan buktinya menjadi bagian Anda sendiri.

$MA \subseteq AM$, Saya akan mengatakan sesuatu seperti "MAKE ARTHUR SPEAK MORE". Tapi mungkin sesuatu yang lain dalam buktinya terasa menjadi "kunci" ide bagi Anda, yang sangat baik. Ini intuisi Anda !)

Saya kira saran saya mungkin berguna untuk sebagian besar matematika, tetapi saya menemukan itu sangat berguna untuk TCS, di mana banyak bukti benar-benar bermuara pada 1-2 ide yang benar-benar baru, dan sisanya adalah sintesis dari ide itu dengan apa yang sudah diketahui.

Berhati-hatilah dengan intuisi. Itu datang dengan banyak pengalaman, sering bisa salah dan benar pada saat yang sama, dan tidak unik. Intinya adalah bahwa setiap orang membawa intuisi mereka sendiri ke masalah berdasarkan zona kenyamanan mereka sendiri, kebutuhan masalah, dan latar belakang mereka. Seperti yang ditunjukkan Tsuyoshi, intuisi adalah banyak kerja keras yang telah disublimasikan menjadi beberapa gambaran mental yang ringkas.

Jadi saran saya adalah: kerjakan saja masalah yang Anda sukai, dan cobalah untuk mengembangkan ide Anda sendiri bahkan jika ada pekerjaan lain di luar sana. Anda akan membangun intuisi dengan cara itu. Dan jika hasilnya tampak membingungkan, itu berarti Anda belum cukup memahaminya, atau mungkin ada hasil yang lebih sederhana yang bersembunyi di suatu tempat di bawahnya, menunggu untuk diungkap.

Karena Anda menghitung game sebagai contoh "intuisi fisik" sementara saya tidak bisa melihat apa pun yang terkait dengan fisika dalam game, saya menganggap bahwa penekanan Anda bukan pada "fisik" tetapi pada "intuisi."

Saya berpendapat bahwa bagian dari tujuan studi (pendidikan atau penelitian) dalam ilmu komputer teoretis adalah untuk mengembangkan intuisi untuk gagasan abstrak terkait dengan perhitungan. Intuisi diperoleh dengan mempelajari dan mengenal konsep tersebut. Saya tidak berharap ada jalan pintas yang bagus.

Sebagai contoh, mahasiswa sarjana akan terkejut dengan ketidakpastian memutuskan masalah (mungkin karena keberadaan bahasa yang tidak dapat dipastikan sudah mengejutkan). Tetapi mempelajari fakta, buktinya, beberapa hasil terkait dan penerapan teknik buktinya yang luas menjadikan hasil mengejutkan ini kurang mengejutkan dan bahkan sangat alami. Saya percaya bahwa hal yang sama berlaku untuk hasil yang lebih rumit.

Mengenai hasil spesifik, saya tidak setuju bahwa tidak ada intuisi sederhana untuk MA⊆AM. (Peringatan: Saya sendiri sedang mempelajari ini dan hasil terkait sendiri, dan saya mungkin mengatakan sesuatu yang salah.) Dalam sistem MA, Merlin harus memberikan jawaban tunggal yang cocok dengan sebagian besar urutan acak yang digunakan oleh Arthur. Kami mengubah sistem sehingga Arthur mengirimkan beberapa (secara polinomi banyak) urutan acak ke Merlin dan Merlin harus memberikan satu jawaban yang cocok untuk semuanya, yang menurut saya seperti hal yang wajar untuk dicoba. Membuktikan kesehatan sistem AM ini adalah aplikasi sederhana dari ikatan Chernoff. Saya tidak berpikir bahwa apa pun dalam hasil ini secara konseptual sulit dipahami.

Terkait dengan Marginal: Pertanyaan Anda mengingatkan saya pada sebuah posting blog yang indah " Abstraksi, intuisi, dan 'tutorial keliru monad' " oleh Brent Yorgey, di mana ia menjelaskan kesulitan berkomunikasi intuisi dengan penjelasan non-fiksi "Monad adalah Burrito." Jika penjelasan di atas tentang bagaimana bukti MA⊆AM bekerja tidak masuk akal, saya mungkin menunjukkan kesalahan yang sama. :(

Jika Anda menghabiskan lima tahun dalam hidup Anda dengan mempelajari konsep teoritis X murni (misalnya, model perhitungan esoterik tertentu), maka akhirnya X menjadi bagian alami dari kehidupan sehari-hari Anda.

Anda akan belajar untuk mengetahui bagaimana X berperilaku, bagaimana rasanya, bagaimana merespons manipulasi Anda, dan di lingkungan seperti apa ia hidup. Anda akan belajar siapa yang menemukannya, kapan, dan mengapa, dan apa yang dilakukan orang lain dengan X, berhasil atau tidak berhasil. Anda akan tahu X sama seperti Anda tahu benda fisik yang Anda temui setiap hari.

Memang, Anda mungkin tahu itu jauh lebih baik daripada hal-hal fisik yang aneh, tidak jelas, tidak dapat diprediksi, dan tidak menentu ... Tapi itu masih jauh , dan saya tidak berpikir ada banyak pintasan ajaib.

Jawaban di sini sudah mencakup sebagian besar saran bagus tentang intuisi. Tetap saya akan memberikan satu lagi, yang berguna ketika mengembangkan intuisi selama penulisan makalah. Ini disarankan oleh guruku sendiri, Hsueh-I Lu, yang menurutku sangat berguna.

Setiap kali hasilnya ditulis, dan kebenarannya tampaknya diverifikasi, tulis ulang seluruh artikel . Kali ini kita harus memaksakan diri kita untuk tidak menggunakan kata atau definisi yang mirip dengan versi sebelumnya. Ini membuat kita berpikir dengan cara yang sama sekali berbeda, dan intuisi baru akan berkembang. Juga, perturbasi setiap parameter yang digunakan dalam kertas, lihat apakah ada set parameter yang berbeda dari yang kami gunakan pada awalnya masih berfungsi. Seringkali beberapa kesalahan terungkap saat menulis ulang artikel. Munculkan ide-ide baru untuk mengatasinya.

Akhirnya, setelah putaran penulisan ulang, kami akan memiliki intuisi bulat yang bagus tentang hasil kami sendiri, dan kami tidak akan terlalu optimis / pesimis terhadap kekuatan ide-ide baru yang disajikan di koran, karena kami telah mencoba beberapa kali, dan jelas bahwa apa yang berhasil dan apa yang tidak.

Metode yang sama berfungsi jika Anda membaca makalah baru, dan ingin mendapatkan lebih banyak intuisi selain yang diberikan oleh membaca.

Dalam kasus saya sendiri, sebagian besar konsep TCS yang saya rasa memiliki intuisi adalah konsep yang saya gunakan melalui hasil praktis. Jika saya menemukan diri saya berevolusi dan menggunakan model atau algoritma yang sama berhasil selama bertahun-tahun, itu cenderung semakin mendorong saya untuk gangguan sampai saya bisa mencari tahu mengapa algoritma itu berhasil. Ini terutama benar jika saatnya untuk menulis ulang - Saya ingin tahu apa esensi TCS dari benda itu, jangan sampai saya kehilangan debu ajaib saat refactoring. Mengetahui semua itu biasanya membutuhkan (bagi saya) penyelaman yang dalam kembali ke tahun 1936 atau lebih, dan menghubungkan apa yang telah saya lakukan dengan konsep-konsep dasar itu. Seorang teman pernah menasehati saya untuk "berpikir seperti mesin turing" ketika saya berada di salah satu penyelaman itu, dan saran itu telah melekat pada saya.