Tas, principā, ir vienīgais problemātiskais scenārijs, ko es šajā sakarā varu iedomāties. Un pat tādā gadījumā runa ir par meklēšanas laiku ar klasisku kanonisko Tjūringa mašīnu, kas izmanto vienu viena bita platuma lenti. Praksē ļoti daudzas sequentially neatrisināmas problēmas piepeši kļūst pat ļoti atrisināmas, iesaistot masveida paralēlismu un citas reālas skaitļošanas tehnikas, kuras parastie teorētiskie Tjūringa mašīnu apraksti neņem vērā.

Jāpiezīmē, ka šeit es pieturos pie maksimāla present-grounded reālisma, kas neapsver hipotētiskas iespējas par tehnikām un iespējām, ko varētu ultramasīvai skaitļošanai izmantot nākotnē.

(Reply to this) (Parent) (Thread)

Eksponenciālie algoritmi ir un paliek eksponenciāli, un parastais paralēlisms tos kvalitatīvi neatrisinās.
Vienīgā no fizikas viedokļa puslīdz ticamā pretinde ir kvantu datori, bet arī tie spēj panākt eksponenciālu uzlabojumu tikai atsevišķām problēmām.

(Reply to this) (Parent) (Thread)

If you can't use a computable problem with adding more computational resources, you aren't adding enough. Pie tam, kā jau sacīju, klasisks universālam meklēšanas algoritmam eksponenciāls pieaugums ir novērojams tikai sliktākajā, tīra brute-force gadījumā.

(Reply to this) (Parent)