Makalah tentang hubungan antara kompleksitas komputasi dan geometri / topologi aljabar?

22

Saya ingin tahu makalah apa yang harus saya baca untuk memahami pertanyaan ini

Koneksi tak terduga ke bidang matematika lain seperti geometri aljabar atau kohomologi yang lebih tinggi. Mungkin bahkan bidang matematika belum berkembang. Mungkin seseorang akan mengembangkan arah yang sama sekali baru untuk matematika untuk menangani pertanyaan P versus NP. -Dari Fortnow 2002

Ungkapan lain dari pertanyaan itu adalah "Makalah apa yang harus saya baca untuk membuat koneksi dari kompleksitas komputasi ke geometri / topologi aljabar?"

Saya telah melihat Teori Kompleksitas Geometrik . Juga makalah dalam Komputasi Quantum Topologis yang telah saya baca cukup makalah yang saya sudah akrab dengan lapangan Apakah saya kehilangan sesuatu?

cc.complexity-theory reference-request gct algebraic-topology Joshua Herman
sumber
1
Bolehkah saya menyarankan perubahan pada judul? Sesuatu seperti "Makalah tentang hubungan antara Kompleksitas Komputasi dan geometri / topologi aljabar".
Kaveh
Bisakah Anda menguraikan sedikit pertanyaan Anda? Saya akan berpikir semua orang akan kehilangan sesuatu dari garis itu jika garis itu benar karena dia berbicara tentang "tidak diketahui". Saya pikir jawaban profesor Suresh di bawah pada batas bawah adalah referensi yang bagus.
vs
2
Anda mungkin juga ingin melihat pertanyaan terkait ini: cstheory.stackexchange.com/questions/2898/…
Martin Schwarz
1
Saya juga menemukan makalah ini cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman

Jawaban:

10
vs.
sumber
Apakah ini contoh eksplisit kohomologi etale? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman
Silakan lihat di sini. www-math.mit.edu/~kedlaya/18.787/intro.pdf
vs
1
Karya Sudan dan Guruswami sebagian besar dikhususkan untuk daftar decoding (yang, juga, menyangkut kode AG juga) - topik yang diangkat pada akhir 90-an dan banyak dikembangkan pada 2000-an. Metode geometri aljabar muncul di 80-an di kertas oleh Goppa, dan dikembangkan oleh Tsfasman dan Vladutc dan banyak lainnya di 90-an. Secara pribadi saya menyarankan makalah: Hoholdt, van Lint, Pellikaan, kode geometri aljabar, 1998.
Artem Pelenitsyn
1
Mengenai AG komputasi, saya akan menyarankan buku-buku karya Cox — Little — O'Shea dan Schenck, tetapi topik ini sedikit tidak relevan dengan “koneksi dari kompleksitas komputasi ke geometri aljabar” yang diminta oleh Joshua.
Artem Pelenitsyn
4

Di Slide 26 , Martin Escardo menyediakan algoritma yang mungkin memberi Anda apa yang Anda cari:

  1. Pergi ke perpustakaan.
  2. Pilih buku tentang topologi.
  3. Pilih teorema.
  4. Terapkan kamus.
  5. Dapatkan teorema dalam perhitungan.

http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf

Lihat juga tulisan ini

NietzscheanAI
sumber
2
Kamus menjadi korespondensi antara istilah dalam topologi (seperti set terbuka) dan komputabilitas (seperti set semi-decidable).
Mitch
mungkin ini seharusnya jawaban yang diterima
Nikos M.
@NikosM. Saya akan terkoyak dengan jawaban pertama dan yang ini serta jawaban yang diterima telah diterima untuk sementara waktu jadi saya lebih suka tidak mengubahnya. Jika ada jawaban yang digabungkan dengan segalanya mungkin tetapi kemudian pertanyaan ini mungkin akan menjadi wiki komunitas.
Joshua Herman
@ JoshuaHerman, tentu saja saya mengerti, meskipun saya sendiri kadang-kadang mengubah jawaban yang diterima ketika pengetahuan saya diperbarui dan jawaban lain yang lebih ke titik pertanyaan muncul. Ngomong-ngomong, tentang topik tersebut, Anda akan menemukan bahwa ada lebih banyak analogi dengan bidang matematika lainnya juga (saya, bukan hanya antara kompleksitas-topologi) Misalnya, area yang memiliki potensi ini (dan terinspirasi oleh topologi) adalah teori kategori
Nikos M.
3

Beberapa referensi baru-baru ini di sini dari Topologi Aljabar, dan UGC hardness- Morse Theory , dan referensi lain tentang Konjektur Game Unik dan Topologi Komputasi . Yang terakhir adalah tentang menutupi ruang grafik, dan "mengangkat" grafik, dan bisa menunjuk ke hubungan yang lebih dalam antara Topologi, dan Konjektur Game Unik.

pengguna3483902
sumber