stringtranslate.com

Тезис Кобэма

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

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

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

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

Ограничения

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

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

Все три связаны и являются общими жалобами на анализ алгоритмов , но они особенно применимы к тезису Кобэма, поскольку он делает явное заявление о практичности. Согласно тезису Кобэма, задача, для которой лучший алгоритм требует n 200 инструкций, считается выполнимой, а задача с алгоритмом, требующим 2 0,00001  n инструкций, невыполнимой — даже если никто не сможет решить пример размера n  = 2 с помощью первого алгоритма, тогда как пример последней задачи размера n  = 10 6 может быть решен без труда. В областях, где практические проблемы имеют миллионы переменных (таких как исследование операций или автоматизация электронного проектирования ), даже алгоритмы O( n 3 ) часто непрактичны. [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, CRC Press.
  5. ^ Алан Кобэм (1965), Внутренняя вычислительная сложность функций (PDF).
  6. ^ Эдмондс, Джек (1965). «Пути, деревья и цветы». Can. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 . S2CID  18909734.
  7. ^ Меран, Жерар (2014). Алгоритмы и сложность . Эльзевир. п. п. 4. ISBN 978-0-08093391-7. Задача считается выполнимой, если ее можно решить за полиномиальное время (как впервые было заявлено в работе Эдмондса [26] [1965, Paths, trees, and flowers]).
  8. ^ Д. Писингер, 2003. «Где сложные задачи о рюкзаке?» Технический отчет 2003/08, Кафедра компьютерных наук, Копенгагенский университет, Копенгаген, Дания, см. [1] (Архивировано 23 ноября 2015 г. на Wayback Machine ), доступ 31 января 2015 г.
  9. ↑ Ротман, Брайан (18 июня 2003 г.). «Преобразует ли цифровой компьютер классическую математику?». Phil. Trans. R. Soc. Lond. A. 361 ( 1809): 1675–1690. Bibcode : 2003RSPTA.361.1675R. doi : 10.1098/rsta.2003.1230. PMID  12952680. S2CID  38600389.