Kompleksitas waktu dengan eksponen irasional?

21

Apakah ada masalah alami dalam P yang terikat waktu berjalan paling dikenal adalah dari bentuk , di mana adalah konstanta irasional ?HAI(nα)α

Andras Farago
sumber
4
Pertanyaan rapi! :)
Michael Wehar
1
lihat juga rasio emas atau dalam waktu berjalanπ . ini bisa dibayangkan menjadi daftar besar ...
vzn
Mengurutkan multiset adalah sekitar nH + n, jadi jika Anda bisa mendapatkan H (entropi) untuk konvergen ke beberapa yang secara teknis memenuhi syarat. Saya tidak akan menyebut itu "alami". Namun mungkin ada beberapa masalah yang lebih alami di mana input dikurangi dengan cara ini. nα-1
KWillets

Jawaban:

22

Meskipun diakui saya belum melakukan analisis, dan ini bukan semata-mata masalah keputusan, saya bersedia untuk bertaruh algoritma penggandaan matriks yang paling dikenal (oleh Coppersmith, Winograd, Stothers, Williams, et al) memiliki eksponen irasional.

Ini dapat dilihat lebih jelas dalam kasus sederhana algoritma Strassen, yang memiliki waktu berjalan .HAI(nlog27)

Dan, ini tidak persis apa yang Anda tanyakan, tetapi Ryan Williams telah menunjukkan bahwa semua algoritma yang memecahkan SAT dalam ruang memerlukan waktu n 2 cos ( π / 7 ) - o ( 1 ) , yang merupakan hal lain yang menarik dan tidak biasa penampilan konstanta irasional dalam TCS.nHai(1)n2cos(π/7)-Hai(1)

Joe Bebel
sumber
3
Algoritma di luar algoritma Strassen tidak benar-benar berjalan di untuk eksponen α yang mereka nyatakan. Sebaliknya, untuk setiap ϵ > 0 mereka berjalan dalam O ϵ ( n α + ϵ ) . Ini disebabkan oleh beberapa batasan yang terlibat dalam memperoleh α . HAI(nα)αϵ>0HAIϵ(nα+ϵ)α
Yuval Filmus
12
Kompleksitas waktu dari algoritma Strassen benar-benar merupakan artefak dari pengulangan Master memecahkan ke Θ ( n log b a ) . Anda dapat menemukan banyak bilangan irasional favorit Anda dengan membuat contoh a dan b dengan nilai yang berbeda. T(n)=SebuahT(n/b)+f(n)Θ(nlogbSebuah)Sebuahb
Huck Bennett
Ya, saya setuju dengan keduanya. Saya pikir saya sudah longgar dengan definisi P, dan belum benar-benar memeriksa apakah eksponen perkalian matriks tidak rasional. Meskipun saya akan terkejut jika mereka rasional, mengingat bagaimana mereka diturunkan. Jauh di dalam, perkalian matriks cepat masih menggemakan metode pembagian dasar dan penaklukan dasar Strassen, meskipun hal ini dijelaskan dalam bahasa tensor sekarang. Sebenarnya, meskipun mudah untuk membangun algoritma seperti yang Anda gambarkan dengan irasional , saya tidak dapat memikirkan algoritma pembagian dan menaklukkan alami lainnya dengan properti seperti itu, selain perkalian. logbSebuah
Joe Bebel
Beberapa algoritma multiplikasi integer memiliki eksponen yang tidak rasional jika saya ingat dengan benar.
Yuval Filmus
Benar, seperti milik Karatsuba. Tapi ini masih berlipat ganda :)
Joe Bebel