Диссертация Кобхэма - Википедия - Cobhams thesis

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

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

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

Статья Джека Эдмондса 1965 года "Дорожки, деревья и цветы"[6] также приписывают определение п с решаемыми проблемами.[7]

Ограничения

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

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

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

Все три связаны между собой и представляют собой общие жалобы на анализ алгоритмов, но они особенно применимы к тезису Кобхэма, поскольку он явно заявляет о практичности. Согласно тезису Кобхэма, проблема, для которой лучший алгоритм принимает п100 инструкции считается выполнимым, и проблема с алгоритмом, который занимает 20.00001 п инструкции невыполнимы - даже если невозможно решить экземпляр размера п = 2 с первым алгоритмом, тогда как экземпляр второй проблемы размера п = 106 можно было решить без труда. В областях, где практические проблемы имеют миллионы переменных (например, Исследование операций или же Автоматизация электронного проектирования ), даже O (п3) алгоритмы часто непрактичны.[9]

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

  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, CRC Press
  5. ^ Алан Кобхэм (1965), Внутренняя вычислительная сложность функций (PDF)
  6. ^ Эдмондс, Джек (1965). «Дорожки, деревья и цветы». Может. J. Math. 17: 449–467. Дои:10.4153 / CJM-1965-045-4.
  7. ^ Меурант, Жерар (2014). Алгоритмы и сложность. п.п. 4. ISBN  978-0-08093391-7. Говорят, что проблема достижимый если ее можно решить за полиномиальное время (как впервые было заявлено Эдмондсом [26] [1965, Пути, деревья и цветы])).
  8. ^ Д. Писингер, 2003. «Где же проблемы с тяжелым рюкзаком?» Технический отчет 2003/08, Департамент компьютерных наук, Копенгагенский университет, Копенгаген, Дания, см. [1] В архиве 2015-11-23 в Wayback Machine, по состоянию на 31 января 2015 г.
  9. ^ Ротман, Брайан (18 июня 2003 г.). «Преобразует ли цифровой компьютер классическую математику?». Фил. Пер. R. Soc. Лондон. А. 361 (1809): 1675–1690. Дои:10.1098 / rsta.2003.1230. PMID  12952680.