|
21. Jun 2012|22:58 |
I agree on the distinction but not on the specification. In practice tractability most frequently can be seen as equal to the upper bound of available computational resources.
Galvenokārt tādēļ, ka "praksē" ir stiepjams jēdziens kā tāds. Tiklīdz mēs esam šaipus computability robežai, jelkura problēma ir atrisināma ar universālo Tjūringa mašīnu galīgā skaitā soļu = galīgā laikā. Tas, ka šis laiks var būt ilgs, netiek apstrīdēts, taču es neredzu, kādēļ tā būtu problēma. |
|