Referensi untuk teknik bukti TCS

38

Apakah ada referensi (daring atau dalam bentuk buku) yang mengatur dan mendiskusikan teorema TCS dengan teknik bukti? Garey dan Johnson melakukan ini untuk berbagai jenis konstruksi widget yang diperlukan untuk bukti kelengkapan NP (terutama dalam bab 3 buku mereka), tetapi saya bertanya-tanya apakah ada sesuatu yang memperlakukan teknik bukti dalam TCS secara lebih luas.

Jadi misalnya, topik mungkin termasuk diagonalisasi, dirinci lebih lanjut oleh jenis konstruksi yang digunakan; bukti berdasarkan sejarah perhitungan; konstruksi tablo; argumen yang tidak dapat dimampatkan, dll. Saya kira saya bisa saja mencincang teori standar teks perhitungan dan mengatur ulang bagian-bagiannya, tetapi akan lebih baik jika ada sesuatu di luar sana yang juga menyediakan beberapa komentar tambahan dan menunjukkan di mana ada kesamaan antara teknik yang sedang bekas.

Untuk memperjelas, karena teks apa pun akan menggunakan bukti, apa yang saya benar-benar tertarik untuk menemukan adalah referensi di mana teknik pembuktian sendiri adalah materi pelajaran yang sebenarnya.

Selain bab 3 dari Garey dan Johnson, berikut adalah contoh parsial lain yang baru saja terlintas di benak saya: di Li dan Vitanyi , di bab 6 mereka membahas metode ketidakmampatan dan memberikan contoh bagaimana menerapkan teknik ini.

reference-request proof-techniques Kurt
sumber
buku ini bagus untuk kompleksitas komputasi cs.princeton.edu/theory/complexity
Marcos Villagra
ini adalah pertanyaan yang luas cakupannya adalah semua bidang! voting untuk ditutup kecuali bisa dipersempit secara signifikan. Juga, kemungkinan besar perlu menjadi wiki komunitas, karena tidak ada jawaban pasti tunggal.
Suresh Venkat
1
Saya tidak mencari daftar teknik pembuktian; Saya berharap sudah ada referensi dari sifat ini di luar sana di mana seseorang dapat mengarahkan saya. Mengapa tidak membiarkannya terbuka sedikit lebih lama sampai lebih banyak mata memiliki kesempatan untuk melihatnya?
Kurt
5
Saya tidak dapat membantu tetapi berpikir bahwa saya disalahpahami di sini. Jika pertanyaannya terlalu luas maka harus ada banyak kemungkinan jawaban. Saya tidak tahu ada tanggapan langsung (jelas, atau saya tidak akan bertanya), dan mungkin hanya beberapa yang parsial.
Kurt
1
Masalahnya adalah bahwa teknik pembuktian dalam subbidang TCS biasanya tidak melanjutkan ke bidang lain. Saya pikir matematikawan biasanya mempelajari bukti dalam kursus mereka untuk mempelajari teknik bukti. Misalnya, diagonalisasi tidak berlaku untuk membuktikan suatu program yang benar, sedangkan invarian sedikit atau tidak digunakan dalam teori komputabilitas; teknik bukti untuk kompleksitas yang diamortisasi hanya relevan dengan subbidang itu. Reduksi tidak biasa dalam penerapannya dalam komputabilitas, kompleksitas, dan kriptografi yang dapat dibuktikan. Google "teorema gratis" untuk teknik yang hanya relevan untuk program dalam bahasa tertentu.
Blaisorblade

Jawaban:

36

Teori Kompleksitas Pendamping oleh Hemaspaandra dan Ogihara . Ini tidak lengkap dalam hal teknik (saya kira tidak ada buku seperti itu), tetapi saya pikir itu memenuhi syarat sebagai jawaban untuk pertanyaan Anda. Inilah judul bab-babnya:

  • Teknik Reducibilitas Diri.
  • Teknik Fungsi Satu Arah.
  • Teknik Tournament Divide and Conquer.
  • Teknik Isolasi.
  • Teknik Pengurangan Saksi.
  • Teknik Interpolasi Polinomial.
  • Teknik Kelompok yang Tidak Dapat Diatasi.
  • Teknik Pembatasan Acak.
  • Teknik Polinomial.
Joshua Grochow
sumber
1
Terima kasih! Dari uraian buku penerbit, "... buku ini --- tidak seperti teks-teks lain tentang kompleksitas --- yang diorganisasikan oleh teknik dan bukan oleh topik" pasti terdengar seperti apa yang ada dalam pikiran saya. (Saya harus mengakui bahwa saya tidak mengenali banyak judul bab itu - buku ini mungkin akan sedikit kasar bagi saya.)
Kurt
25

Inilah buku lain di mana bab-babnya lebih fokus pada teknik pembuktian.

"Combinatorics Extremal Dengan Aplikasi dalam Ilmu Komputer", oleh Stasys Jukna. Ini buku yang bagus dan mencakup banyak kombinatorik yang mungkin Anda butuhkan di TCS. Tentu saja pokok bahasannya tidak termasuk diagonalisasi, tabloid, dll., Tetapi itu adalah kumpulan teknik kombinatorial yang rapi mencari aplikasi (dan di berbagai tempat dalam teks, aplikasi dijabarkan).

"Draf awal" edisi kedua tersedia di sini .

Ryan Williams
sumber
Terima kasih, itu terlihat seperti teks yang sangat berguna - saya telah melanjutkan dan memesan sendiri salinannya.
Kurt
15

Buku "Permata Ilmu Komputer Teoritis" adalah cara yang baik untuk mempelajari banyak teknik yang berbeda (walaupun Anda melihat masing-masingnya hanya diterapkan satu kali):

http://www.calvin.edu/~rpruim/publications/gems/

Dave Doty
sumber
Itu terdengar seperti teks yang menarik, tetapi saya hanya mencoba mencarinya di Amazon ( amazon.com/Gems-Theoretical-Computer-Science-Sch%C3%B6ning/dp/… ) dan saya harus melakukan pengambilan ganda! Harus kehabisan cetakan dan sangat berharga.
Kurt
15

Ada wiki yang didedikasikan untuk teknik pembuktian yang berbeda: http://www.tricki.org/ (tampaknya terinspirasi oleh Timothy Gowers).

ilyaraz
sumber
Ah, itu berpotensi tepat seperti yang saya harapkan. Saya melihat bahwa mereka memiliki entri placeholder untuk kompleksitas komputasi dan algoritma, tetapi sayangnya, sejauh ini mereka kosong.
Kurt
Anda dapat meningkatkan bagian ini, saya pikir.
ilyaraz
Memang, saya mungkin akan belajar topik yang lebih baik dengan menulis entri baru daripada dengan membaca yang sudah ada ... proyek jangka panjang yang bagus, mungkin.
Kurt
13

Teknik-teknik lain yang berguna dalam banyak bagian ilmu komputer teoritis:

Noga Alon dan Joel H. Spencer, Metode Probabilistik (edisi ke-3), Wiley, ISBN 0470170204.

András Salamon
sumber
12

S. Fenner, L. Fortnow, S. Kurtz, dan L. Li. Toolkit pembangun oracle. Informasi dan Komputasi, 182 (2): 95-136, 2003. (juga tersedia dari beranda Lance ).

Ini pada dasarnya adalah makalah survei tentang penggunaan kedermawanan dalam membangun "perancang oracle" (yaitu, peramal dirancang untuk memiliki berbagai sifat). Meskipun ini sebuah makalah, saya pikir itu memenuhi syarat sebagai jawaban untuk pertanyaan karena berfokus pada teknik dan penggunaannya, daripada hasil tertentu. [Tapi ini jauh lebih spesifik daripada Compory Teori Teori Kompleksitas, itulah sebabnya saya pikir itu harus dalam jawaban yang terpisah.]

Joshua Grochow
sumber
7

Kami telah memulai beberapa pertanyaan referensi tentang cs.SE yang mencakup masalah TCS yang khas (sejauh ini pengantar). Selain relevansi umum, beberapa jawaban berisi metode yang mungkin tidak diketahui oleh setiap peneliti, misalnya dalam hal ini:

Kami juga memiliki Bagaimana tidak menyelesaikan P = NP? yang lebih lanjut tentang anti-teknik.

Raphael
sumber
1

Dengan semangat yang sama dari catatan Sanjeev Arora yang diposting @umar, saya suka catatan kuliah dan latihan Madhur Tulsiani untuk kelas "Matematik Alat" yang diposting di halaman web kursus . Selain materi yang luar biasa dari Arora, catatan-catatannya memiliki liputan yang bagus tentang teori grafik spektral serta metode pembaruan bobot multiplikatif.

rahulmehta95
sumber