Pendekatan kohomologis untuk kompleksitas boolean

33

Beberapa tahun yang lalu, ada beberapa karya Joel Friedman yang menghubungkan batas bawah dengan kohomologi Grothendieck (lihat makalah: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Apakah garis pemikiran ini membawa wawasan baru ke dalam kompleksitas boolean, atau apakah itu tetap menjadi keingintahuan matematis?

Marcin Kotowski
sumber
4
Saya sangat penasaran melihat jawabannya. Tentu saja, yang paling mudah adalah dengan mengirim email kepada Joel Friedman :)
Suresh Venkat

Jawaban:

28

Saya berkorespondensi dengan Joel Friedman sekitar 3 tahun yang lalu tentang topik ini. Pada saat itu dia mengatakan bahwa pendekatannya tidak mengarah pada wawasan baru yang signifikan terhadap teori kompleksitas, meskipun dia masih berpikir itu adalah taktik yang menjanjikan.

Pada dasarnya, Friedman mencoba untuk mengulangi masalah kompleksitas sirkuit dalam bahasa berkas gandum pada topologi Grothendieck. Harapannya adalah bahwa proses ini akan memungkinkan intuisi geometri untuk diterapkan pada masalah menemukan rangkaian batas bawah. Meskipun tentu perlu dicoba untuk melihat apakah jalan ini mengarah ke mana saja, ada alasan heuristik untuk bersikap skeptis. Intuisi geometris bekerja paling baik dalam konteks varietas halus, atau hal-hal yang cukup mirip dengan varietas halus yang intuisi tidak sepenuhnya rusak. Dengan kata lain, Anda memerlukan beberapa struktur agar intuisi geometri mendapatkan pijakan. Tapi sirkuit batas bawah pada dasarnya harus menghadapi perhitungan sewenang-wenang, Yang sulit untuk dianalisis secara tepat karena mereka tampaknya begitu terstruktur. Friedman mengakui di depan bahwa topologi Grothendieck yang ia anggap sangat kombinasi, dan jauh dari objek studi yang biasa dalam geometri aljabar.

Sebagai komentar sampingan, saya akan mengatakan bahwa penting untuk tidak terlalu bersemangat tentang sebuah ide hanya karena menggunakan mesin asing yang bertenaga tinggi. Mesin mungkin sangat efektif dalam memecahkan masalah yang dirancang untuk itu, tetapi agar berguna untuk menyerang masalah sulit yang diketahui di domain lain, perlu ada beberapa argumen yang meyakinkan mengapa mesin asing disesuaikan dengan baik untuk mengatasi masalah mendasar. hambatan dalam masalah bunga.

Timothy Chow
sumber
4
Tentu saja upaya Mulmuley ada di sepanjang garis "serupa" dalam arti menggunakan "struktur halus", tetapi dia sedang melihat masalah yang mengakui invarian geometris yang bagus untuk memulai.
Suresh Venkat
2
@ Suresh: Anda benar bahwa pendekatan Mulmuley-Sohoni berbeda, tetapi masalah mendasar dalam mengatasi perhitungan sewenang-wenang masih mengintai di latar belakang, jadi wajar jika kita bertanya bagaimana seseorang mengharapkan untuk mengatasinya. Saat ini saya tidak berpikir ada yang benar-benar tahu, itulah sebabnya orang-orang GCT tidak menjanjikan terobosan spektakuler dalam waktu dekat.
Timothy Chow
memang. Sangat menarik untuk melihat makalah STOC 2011 yang menggunakan GCT untuk batasan penggandaan matriks (dan Ketan telah menyebutkan hasil ini dalam tutorialnya di FOCS)
Suresh Venkat
1
@ Suresh: Jika Anda berbicara tentang kertas Buergisser / Ikenmeyer, saya pikir ini memberi tahu lebih banyak tentang batas-batas pendekatan GCT daripada tentang bagaimana membuktikan batas bawah.
5501
1
@Neel, saya tidak punya jawaban, tapi saya ingin tahu apakah ini mungkin pantas pertanyaannya sendiri.
Suresh Venkat
16

Saya pikir Timothy Chow benar. Saya memiliki daftar cucian pribadi saya sendiri mengenai ide-ide yang melibatkan varietas "halus", atau konsep-konsep seperti penghitungan komponen atau monomial yang terhubung dengan beberapa anak tangga paling bawah dari "tangga kohomologi" --- semuanya ditunjukkan bukan oleh kekerasan yang diprediksi oleh ( variasi pada) konstruksi Mayr-Meyer menunjukkan EXPSPACE-kelengkapan berbagai masalah terkait GCT. Satu-satunya kekurangan saya pada paragraf terakhirnya adalah saya pikir beberapa jenis mesin bertenaga tinggi diperlukan ...!

Kenneth W. Regan
sumber