Judulnya sedikit menyesatkan: tapi semoga pertanyaannya bukan:
Hasil baru Grønlund dan Pettie menunjukkan bahwa 3SUM hanya memiliki kompleksitas pohon keputusan membuat saya bertanya-tanya:
Apakah ada contoh sederhana dari masalah dengan kompleksitas pohon keputusan tetapi mengakui batas bawah (dalam model yang lebih rinci) dari ?
Dengan kata lain, bagaimana seharusnya hasil pada 3SUM mengubah pandangan kita tentang kemungkinan mendapatkan batas yang jauh lebih rendah daripada pada kompleksitas masalah?
cc.complexity-theory
machine-models
decision-trees
Suresh Venkat
sumber
sumber
Jawaban:
sumber
sumber