pro.algorithms
Конечно, очень любопытно как космические корабли бороздят Большой театр про
транзисторы и т.п., а вот заданному мной вопросу у кого-нибудь есть хоть какие-то идеи? ;)
4 ответов
скорее нет чем да - любая такая теория будет слишком привязана к конкретной вычислительной платформе
Yaroslav
Schekin
Автор вопроса
скорее нет чем да - любая такая теория будет слишк...
Почему бы это? Основные абстрактные машины хорошо известны, их ограниченные константными ресурсами варианты представить несложно. И я же спрашиваю про общий подход к построению/заданию подобных мер. Кстати, именно эта конструкция используется в учебниках (по теории сложности и т.п.) для демонстрации того, что любой реальный компьютер с константными ограниченными ресурсами теоретически a) не является МТ и б) вообще эквивалентен конечному автомату. Но в них она далее никак не развивается, вот в чём проблема.
Почему бы это? Основные абстрактные машины хорошо...
Потому что в конечном случае нельзя определять классы сложности с точностью до мультипликативной константы - а значит и спрятать детали конкретной реализации абстрактного вычислителя некуда
Yaroslav
Schekin
Автор вопроса
Потому что в конечном случае нельзя определять кла...
А какие вообще детали реализации конкретного вычислителя тут релевантны, кроме размера/дины кодировки состояний автомата и символов стека/"ленты" и т.п.? > Кроме того, в таком виде не очень понятно, как определять сводимость задач Сходу не скажу... но почему бы не использовать примерно те же подходы?
Похожие вопросы
Обсуждают сегодня