Apakah ada masalah alami dalam P yang terikat waktu berjalan paling dikenal adalah dari bentuk , di mana adalah konstanta irasional ?
cc.complexity-theory
time-complexity
polynomial-time
Andras Farago
sumber
sumber
Jawaban:
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 .O ( 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.no ( 1 ) n2 cos( π/ 7)-o(1)
sumber