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?
cc.complexity-theory
lower-bounds
circuit-complexity
boolean-functions
Marcin Kotowski
sumber
sumber
Jawaban:
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.
sumber
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 ...!
sumber