Диссертация Кобэма
Диссертация Кобэма , также известная как диссертация Кобэма-Эдмондса (названная в честь Алана Кобэма и Джека Эдмондса ), [ 1 ] [ 2 ] [ 3 ] утверждает, что вычислительные задачи могут быть реально решены на некотором вычислительном устройстве только в том случае, если они могут быть решены за полиномиальное время ; есть, если они принадлежат классу сложности P. то [ 4 ] Говоря современным языком, он идентифицирует проблемы с классом сложности P. решаемые
Формально сказать, что проблема может быть решена за полиномиальное время, — значит сказать, что существует алгоритм, который, учитывая n -битный экземпляр проблемы в качестве входных данных, может дать решение за время O( n с ), используя обозначение big-O и где c является константой, которая зависит от проблемы, но не от конкретного случая проблемы.
Статья Алана Кобэма 1965 года под названием «Внутренняя вычислительная сложность функций». [ 5 ] — одно из первых упоминаний понятия класса сложности P , состоящего из задач, решаемых за полиномиальное время. Кобэм предположил, что этот класс сложности является хорошим способом описания набора реально вычислимых задач.
Статья Джека Эдмондса 1965 года «Дорожки, деревья и цветы». [ 6 ] ему также приписывают выявление P с разрешимыми проблемами. [ 7 ]
Ограничения
[ редактировать ]
Хотя диссертация Кобэма является важной вехой в развитии теории вычислительной сложности , она имеет ограничения применительно к практической осуществимости алгоритмов. По сути, в тезисе говорится, что « P » означает «легкий, быстрый и практичный», а «не в P » означает «тяжелый, медленный и непрактичный». Но это не всегда так, потому что этот тезис абстрагирует некоторые важные переменные, которые на практике влияют на время выполнения:
- Он игнорирует постоянные факторы и члены более низкого порядка.
- Он игнорирует размер экспоненты. Теорема об иерархии времени доказывает существование проблем в P, требующих сколь угодно больших показателей.
- Он игнорирует типичный размер ввода.
Все три взаимосвязаны и представляют собой общие претензии к анализу алгоритмов , но они особенно применимы к тезису Кобэма, поскольку он явно заявляет о практичности. Согласно тезису Кобэма, задача, для решения которой лучший алгоритм принимает n 200 инструкций считается выполнимой, а задача с алгоритмом, требующим 2 0,00001 н инструкции невыполнимы - даже несмотря на то, что с помощью первого алгоритма никогда не удастся решить экземпляр размера n = 2, тогда как экземпляр второй проблемы размера n = 10 6 можно было решить без труда. В областях, где практические задачи имеют миллионы переменных (например, исследование операций или автоматизация электронного проектирования ), даже O( n 3 ) алгоритмы часто непрактичны. [ 9 ]
Отдельное соображение состоит в том, что во многих случаях часто довольствуются приближенными решениями, если точное решение найти невозможно. Например, многие подозревают, что задача коммивояжера неразрешима точно за полиномиальное время (она NP-трудна ), но хорошие решения можно получить за полиномиальное время с помощью таких методов, как алгоритм Кристофидеса .
Ссылки
[ редактировать ]- ^ Одед Голдрейх (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 128, ISBN 978-0-521-88473-0 .
- ^ Декстер Козен (2006), Теория вычислений , Биркхойзер, стр. 4, ISBN 978-1-84628-297-3 .
- ^ Эгон Бёргер (1989), Вычислимость, сложность, логика , Elsevier, стр. 225, ISBN 978-0-444-87406-1 .
- ^ Гомер, Стивен; Селман, Алан Л. (1992), «Теория сложности» , в Кенте, Алан; Уильямс, Джеймс Г. (ред.), Энциклопедия компьютерных наук и технологий , том. 26, ЦРК Пресс .
- ^ Алан Кобэм (1965), Внутренняя вычислительная сложность функций (PDF) .
- ^ Эдмондс, Джек (1965). «Дорожки, деревья и цветы» . Может. Дж. Математика . 17 : 449–467. дои : 10.4153/CJM-1965-045-4 . S2CID 18909734 .
- ^ Меран, Жерар (2014). Алгоритмы и сложность . Эльзевир. п. п. 4 . ISBN 978-0-08093391-7 .
Задача считается выполнимой, если ее можно решить за полиномиальное время (как впервые было сказано Эдмондсом [26] [1965, «Пути, деревья и цветы]»).
- ^ Д. Пизингер, 2003. «Где проблемы с твердым рюкзаком?» Технический отчет 2003/08, факультет компьютерных наук Копенгагенского университета, Копенгаген, Дания, см. [1] ( архивировано 23 ноября 2015 г. на Wayback Machine ), по состоянию на 31 января 2015 г.
- ^ Ротман, Брайан (18 июня 2003 г.). «Изменит ли цифровой компьютер классическую математику?». Фил. Пер. Р. Сок. Лонд. А. 361 (1809): 1675–1690. Бибкод : 2003RSPTA.361.1675R . дои : 10.1098/rsta.2003.1230 . ПМИД 12952680 . S2CID 38600389 .