Apa jenis latar belakang matematika yang diperlukan untuk teori kompleksitas?

79

Saat ini saya seorang mahasiswa sarjana, yang akan lulus tahun ini. Setelah lulus, saya sedang mempertimbangkan untuk bekerja menuju master / PhD TCS. Saya mulai bertanya-tanya bidang matematika apa yang dianggap membantu TCS, khususnya teori kompleksitas (klasik).

Bidang apa yang menurut Anda penting untuk seseorang yang ingin mempelajari teori kompleksitas? Apakah Anda tahu ada buku teks bagus yang membahas bidang-bidang ini dan jika ya, harap sertakan tingkat kesulitannya (pengantar, lulusan, dll.).

Jika Anda menganggap bidang yang tidak banyak digunakan dalam teori kompleksitas tetapi Anda menganggapnya penting untuk TCS, silakan juga merujuknya.

cc.complexity-theory soft-question advice-request chazisop
sumber
14
Saya sarankan Anda mulai membaca teks standar tentang teori kompleksitas, seperti Arora / Barak atau Papadimitriou, dan setiap kali Anda mengalami kesulitan karena Anda tidak mengerti matematika, cobalah mempelajari matematika yang terkait secara rinci sebelum melanjutkan.
Robin Kothari
8
Setelah Anda melakukan apa yang disarankan Robin, mulailah mengerjakan beberapa masalah kecil yang terbuka. Anda akan merasa terstimulasi untuk mempelajari matematika yang ada di baliknya. Sebagai seorang mahasiswa pascasarjana, saya merasa tidak efisien untuk belajar beberapa bidang matematika hanya demi belajar.
Alessandro Cosentino

Jawaban:

53

Jika Anda melihat jawaban untuk pertanyaan TCS StackExchange ini , Anda akan melihat bahwa ada kemungkinan bahwa hampir semua bidang matematika dapat menjadi penting dalam teori kompleksitas. Jadi, jika Anda benar-benar tertarik pada beberapa bidang matematika yang tampaknya tidak berhubungan, lanjutkan saja dan pelajarilah. Jika pernah menjadi relevan dengan teori kompleksitas, Anda akan menjadi salah satu dari sedikit teori kompleksitas yang memahaminya.

Peter Shor
sumber
20
Jawaban ini tidak berarti Anda tidak boleh mempelajari bidang yang kami tahu terkait (lihat jawaban lain). Saya akan mengatakan ini termasuk aljabar linier, teori graf, teori probabilitas, aljabar abstrak dasar, dan logika dasar.
Peter Shor
6
≠
34

Anda harus menambahkan buku Dexter Kozen pada teori perhitungan ke daftar Anda. Mencakup dasar-dasar teori kompleksitas dengan sangat efektif, dan format kuliah singkatnya bagus.

Dalam hal latar belakang matematika, selain apa yang disebutkan di atas:

  • Teori probabilitas
  • Aljabar linier dan aljabar abstrak
  • teori grafik
  • logika dasar

Saya pikir Anda tidak perlu menjadi ahli dalam topik ini untuk memulai, tetapi jelas membantu memiliki tingkat kenyamanan tertentu.

Suresh Venkat
sumber
32

∙AC0

Ini (setahu saya) satu-satunya buku yang diterbitkan yang membahas 'metode aljabar linier dalam kombinatorik' secara mendalam - alat yang bagus dan kuat untuk diketahui. Ada draft naskah Babai dan Frankl yang jauh lebih mendalam, tetapi itu tidak dipublikasikan atau online:

https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science

∙

Andy Drucker
sumber
2
Sejalan dengan itu, saya ingin menunjukkan panduan yang ditulis dengan indah untuk metode entropi, "Entropy and Counting," oleh Jaikumar Radhakrishnan. Metode entropi adalah salah satu dari alat apik yang sangat memuaskan untuk diterapkan ketika peluang yang tepat datang.
arnab
27

Jawaban sebelumnya sudah mendaftar yang dasar: teori probabilitas, kombinatorik, aljabar linier, aljabar abstrak (bidang terbatas, teori grup, dll).

Saya akan menambahkan:

Analisis Fourier , lihat, misalnya, kursus Ryan O'Donnel: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Teori pengkodean , lihat kursus Madhu Sudan: http://people.csail.mit.edu/madhu/coding/course.html

Teori informasi , buku standarnya adalah Elements of Information Theory: http://www.amazon.com/Elements-Information-Theory-Tel Telecommunications-Processing/dp/ 0471241954

Ada juga teori representasi, jalan-jalan acak, dan banyak lagi yang mungkin saya lupakan ...

Dana Moshkovitz
sumber
5
Sebagian besar hal-hal yang baru saja Anda pelajari saat Anda pergi, tergantung di mana penelitian / kehidupan membawa Anda: dari kursus, dari kuliah, dari kolaborator, dari kertas, dll.
Dana Moshkovitz
22

Terlepas dari hal-hal dasar, mungkin:

  • Combinatorics - Anda mungkin menemukan diri Anda menghitung hal-hal secara teratur
  • Stochastics - Untuk analisis kasus rata-rata dan algoritma acak

Saya suka Matematika Beton oleh Knuth. Ini memberikan gambaran umum / pengetahuan dasar dari banyak alat penting.

Jika Anda suka menghasilkan fungsi (lihat fungsi generasi oleh Wilf) sebagai alat, analisis kompleks juga berguna.

Raphael
sumber
Saya suka Matematika Beton, tapi ini agak esoteris. Saya akan merekomendasikan buku yang lebih utama dulu, seperti "Combinatorics" dari Cameron.
Emil
7
Inilah kesan saya - Beton Matematika tampaknya menjadi buku yang luar biasa untuk belajar bagaimana melakukan analisis algoritma yang tepat (atau hampir tepat), keahlian Knuth. Jika itu yang ingin Anda lakukan, teruskan. Tetapi perlu diketahui bahwa sebagian besar makalah teori kompleksitas memberikan batas yang kurang tepat, sehingga teknik CM kurang relevan.
Andy Drucker
1
Beberapa orang mungkin mengatakan ini adalah karena ahli teori kompleksitas adalah gelandangan malas. Tapi saya pikir itu karena (a) batas yang tepat dapat menjadi lebih banyak upaya daripada nilainya, (b) sering ada kesenjangan besar antara batas atas dan bawah yang diketahui sehingga penyempurnaan kecil di kedua sisi tampaknya nilainya kecil.
Andy Drucker
Saya harus mengatakan, ada segala macam hal keren dalam buku ini - komentar saya terutama menyangkut materi tentang solusi yang tepat dari penjumlahan dan hubungan perulangan.
Andy Drucker
22

Sanjeev Arora memiliki dokumen yang bagus untuk kursus pascasarjana (untuk siswa tahun pertama) yang dia ajarkan disebut "theorist's toolkit," yang memiliki banyak bahan dasar yang harus diketahui oleh siswa teori. Banyak hal yang bisa Anda tunggu sampai lulus sekolah untuk belajar, tetapi ini akan memberi Anda gagasan yang baik tentang apa yang perlu Anda ketahui dan beberapa prasyarat.

Lev Reyzin
sumber
20

Paradigma yang umum, walaupun tentu saja tidak universal, bagi banyak peneliti sukses di komunitas TCS adalah sebagai berikut: Mengetahui beberapa dasar di tingkat sarjana, seperti logika, aljabar linier, probabilitas, optimisasi, teori grafik, kombinatorik, aljabar abstrak dasar. Selain itu, jangan memaksakan diri Anda untuk mempelajari hal lain sampai Anda benar-benar berpikir Anda perlu memecahkan masalah yang telah Anda perjuangkan selama berbulan-bulan, atau jika Anda berpikir Anda akan benar-benar menikmati belajar sesuatu demi hal itu.

"Bagaimana saya tahu bahwa saya membutuhkannya jika saya belum pernah melihatnya sebelumnya?", Anda bertanya? Pertanyaan bagus. Kadang-kadang Anda beruntung dan merasakannya: "Anda tahu, sub-masalah yang saya coba atasi ini terdengar sangat mirip dengan transformasi Fourier yang tidak pernah diam Fred. Aku harus memeriksanya atau menjebak Fred di kamar dan minta dia lari cepat ke dasar-dasarnya. " Di lain waktu, Anda menjebak sekelompok orang yang lebih berpengetahuan daripada diri Anda sendiri di sebuah ruangan, mengatakan dengan memberikan ceramah seminar atau sesuatu, dan merengek tentang bagaimana Anda tidak bisa menyelesaikan masalah ini sampai Fred berdentang dengan "Hei, saya bertaruh Anda bahwa Anda dapat menyelesaikan ini dengan Analisis Fourier. Mari saya tunjukkan caranya. " Pada akhirnya, Anda mendapatkan kertas bersama dengan Fred, Anda belajar sesuatu yang baru, dan Anda dan Fred adalah teman terbaik sekarang dan pergi minum setiap Sabtu malam.

TCSgradstudent
sumber
18

Saya pikir daftar bidang matematika yang tidak berguna akan jauh lebih pendek daripada daftar bidang yang! Saya tidak bisa memikirkan apa pun.

Pelajari matematika apa pun yang tampak menarik, dan / atau apa pun yang Anda butuhkan saat ini. Bahkan jika Anda tidak menggunakannya secara langsung, itu akan membantu Anda mempelajari hal-hal lain yang Anda lakukan.

Jeffε
sumber
4
Saya akan jawaban kedua ini. Apa pun matematika yang menurut Anda paling menarik akan memandu Anda ke masalah apa yang paling menarik serta masalah yang cocok untuk Anda selesaikan.
Derrick Stolee
12

Saya merekomendasikan untuk melihat buku-buku ini:

Juga, topik dalam konferensi MFCS (Yayasan Matematika Ilmu Komputer) dapat mengarahkan Anda ke latar belakang seperti apa yang mungkin Anda butuhkan. (Peringatan: konferensi mencakup topik yang sangat canggih. Anda tidak perlu menguasainya. Hanya mencoba untuk mendapatkan gambaran besarnya.)

MS Dousti
sumber
9

Teori bilangan belum disebutkan, tetapi ini adalah alat yang sangat penting untuk banyak konstruksi teori kriptografi dan kompleksitas.

arnab
sumber
6

Teori representasi kelompok terbatas (juga bidang terbatas) dapat secara mengejutkan bermanfaat untuk berbagai tugas, termasuk:

  • algoritma penggandaan matriks ( Cohn - Kleinberg-Szegedy-Umans )

  • membangun kode yang dapat didekodekan secara lokal (lihat mis. makalah ini oleh Klim Efremenko)

  • aplikasi dalam komputasi kuantum (Masalah Subkelompok Tersembunyi untuk kelompok yang bukanabel, metode musuh multiplikasi)

Sn

Marcin Kotowski
sumber
jangan lupa konstruksi deterministik dari grafik expander
Sasho Nikolov
Maksud Anda konstruksi aljabar menggunakan properti (T) a la Lubotzky? Dalam hal ini, ini rasa agak berbeda dari contoh di atas (jangan gunakan irreps dari grup hingga).
Marcin Kotowski
4

Saya sarankan membaca buku Garey dan Johnson

Komputer dan Daya Tarik: Panduan untuk Teori Kelengkapan NP .

Ini dapat dibaca dengan latar belakang matematika yang sangat sedikit. Saya pikir buku ini menyenangkan untuk dibaca, dan saya akan merekomendasikannya sebagai buku pertama tentang Papadimitriou dan Arora / Barak. Setelah Anda membaca ini, Anda dapat membaca buku-buku lain dan mengidentifikasi berbagai bit matematika yang Anda butuhkan untuk memahami topik-topik lanjutan yang Anda minati.

Emil
sumber
1
Saya belajar kompleksitas dari buku ini, tetapi merasa tidak seimbang, dengan banyak detail yang rumit tapi akhirnya tidak penting, namun tidak memiliki cakupan masalah yang penting bahkan pada saat buku itu ditulis. Di sisi lain, itu kadang-kadang merupakan karya referensi penting. Sebaliknya, teks Kozen yang disebutkan dalam jawaban lain jelas, komprehensif dan modern.
András Salamon
1

Sekali waktu program tingkat sarjana CS464 (2002) di UWaterloo CS menggunakan Kompleksitas Komputasi Christos H. Papadimitriou , Addison-Wesley, 1994.

Latar belakang topik yang tercantum termasuk mesin Turing, ketidakpastian, kompleksitas waktu, dan NP-kelengkapan.

Untuk latar belakang, telusuri perpustakaan Anda di dekat QA267.G57 (Goddard's Memperkenalkan teori perhitungan , berdasarkan sekilas cepat membaca atau dua dan ketersediaannya bagi saya, tampaknya menutupi sisi CS latar belakang; Saya punya perasaan beberapa set dan grup teori dari sisi matematika murni juga akan berguna.)

wah0
sumber
2
Saya berharap memiliki cukup reputasi untuk memilih. Mengapa referensi ke satu universitas dan perpustakaannya?
Alessandro Cosentino
2
FWIW, QA267.G57 adalah nomor panggilan Library of Congress, yang merupakan standar perpustakaan yang banyak digunakan. Ini tidak khusus untuk University of Waterloo (kecuali mungkin untuk angka terakhir).
Emil Jeřábek