Диссертация Кобэма

Тезис, в котором говорится, что вычислительные проблемы могут быть вычислены только за полиномиальное время.

Тезис Кобэма , также известный как тезис Кобэма-Эдмондса (названный в честь Алана Кобэма и Джека Эдмондса ), ^{[1] [2] [3]} утверждает, что вычислительные задачи могут быть реально решены на некотором вычислительном устройстве, только если они могут быть вычислены за полиномиальное время. ; то есть, если они принадлежат классу сложности P. ^[4] Говоря современным языком, он идентифицирует решаемые проблемы с классом сложности P .

^{Формально сказать} , что проблема может быть решена за полиномиальное время, — значит сказать, что существует алгоритм, который, учитывая n -битный экземпляр проблемы в качестве входных данных, может дать решение за время O( nc ), используя большой Обозначение -O , где c является константой, которая зависит от проблемы, но не от конкретного случая проблемы.

Статья Алана Кобэма 1965 года под названием «Внутренняя вычислительная сложность функций» ^[5] является одним из первых упоминаний концепции класса сложности P , состоящего из задач, решаемых за полиномиальное время. Кобэм предположил, что этот класс сложности является хорошим способом описания набора реально вычислимых задач.

В статье Джека Эдмондса 1965 года «Тропы, деревья и цветы» ^[6] также приписывают определение P как решаемых проблем. ^[7]

Ограничения

На графике показано время решения задачи в миллисекундах (мс) в зависимости от размера задачи n для задач о рюкзаке, решенных с помощью современного специализированного алгоритма с использованием компьютера Pentium III 933 МГц (в среднем по 100 экземплярам, ​​данные Pisinger ^{[ 8]} ). Подбор квадратного уравнения предполагает, что эмпирическая алгоритмическая сложность для примеров с 50–10 000 переменных равна O((log  n ) ² ), несмотря на наличие экспоненциальной оценки сложности в наихудшем случае в теории.

Хотя диссертация Кобэма является важной вехой в развитии теории вычислительной сложности , она имеет ограничения применительно к практической осуществимости алгоритмов. По сути, в тезисе говорится, что « P » означает «легкий, быстрый и практичный», а «не в P » означает «тяжелый, медленный и непрактичный». Но это не всегда так, потому что этот тезис абстрагирует некоторые важные переменные, которые на практике влияют на время выполнения:

• Он игнорирует постоянные факторы и члены более низкого порядка.
• Он игнорирует размер экспоненты. Теорема об иерархии времени доказывает существование проблем в P , требующих сколь угодно больших показателей.
• Он игнорирует типичный размер ввода.

Все три взаимосвязаны и представляют собой общие претензии к анализу алгоритмов , но они особенно применимы к тезису Кобэма, поскольку он явно заявляет о практичности. Согласно тезису Кобэма, задача, для решения которой лучший алгоритм требует n ²⁰⁰ инструкций, считается осуществимой, а задача с алгоритмом, требующим 2 ^{0,00001  n} инструкций, невыполнимой, даже если  с помощью первого алгоритма никогда не удастся решить задачу размера n = 2. , тогда как экземпляр последней задачи размера n  = 10 ⁶ можно было решить без труда. В областях, где практические задачи имеют миллионы переменных (например, исследование операций или автоматизация электронного проектирования ), даже алгоритмы O( n ³ ) часто непрактичны. ^[9]

Отдельное соображение состоит в том, что во многих случаях часто довольствуются приближенными решениями, если точное решение найти невозможно. Например, многие подозревают, что задача коммивояжера неразрешима точно за полиномиальное время (она NP-трудна ), но хорошие решения можно получить за полиномиальное время с помощью таких методов, как алгоритм Кристофидеса .

Рекомендации

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