Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Ограничения [ править ]

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

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

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

Все три связаны между собой и представляют собой общие претензии к анализу алгоритмов , но они особенно применимы к тезису Кобхэма, поскольку в нем делается явное заявление о практичности. Согласно тезису Кобхэма, задача, для которой лучший алгоритм требует n 100 инструкций, считается выполнимой, а проблема с алгоритмом, который принимает 2 0,00001 n инструкций, - невыполнимой - даже при том, что невозможно решить экземпляр размера n = 2 с помощью первого алгоритма , в то время как пример последней задачи размера n = 10 6 может быть решен без труда. В областях, где практические проблемы имеют миллионы переменных (например, исследования операцийили Electronic Design Automation ), даже O ( n 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. DOI : 10,4153 / CJM-1965-045-4 .
  7. ^ Meurant, Gerard (2014). Алгоритмы и сложность . п. п. 4 . ISBN 978-0-08093391-7. Проблема называется выполнимой, если она может быть решена за полиномиальное время (как было впервые заявлено в Эдмондсе [26] [1965, Пути, деревья и цветы]).
  8. ^ D. Pisinger, 2003. "Где же проблемы с тяжелым рюкзаком?" Технический отчет 2003/08, Департамент компьютерных наук, Копенгагенский университет, Копенгаген, Дания, см. [1] Архивировано 23 ноября 2015 г. на Wayback Machine , по состоянию на 31 января 2015 г.
  9. ↑ Ротман, Брайан (18 июня 2003 г.). «Преобразует ли цифровой компьютер классическую математику?». Фил. Пер. R. Soc. Лондон. . 361 (1809): 1675–1690. DOI : 10,1098 / rsta.2003.1230 . PMID 12952680 .