|
21. Jun 2012|20:24 |
Es šādā sakarā drīzāk runātu par resursietilpības problēmu.
Algoritmiskā jeb Kolmogorova sarežģītības metrika vispāri neatļauj neko, jo nav skaitļojama (computable), taču tās tuvākie atvasinājumi, kā logaritmiskā Kt metrika, ir skaitļojami un redukciju tajos var pārvērst par reversu Levina meklēšanu. Tas gan tik un tā ir ārkārtīgi resursus prasošs algoritms, taču tas nav nedz uncomputable, nedz intractable. |
|