Тезис Кобхэма - Cobham's thesis

Не путать с теоремой Кобэма .

Тезис Кобхэма , также известный как тезис Кобхэма – Эдмондса (названный в честь Алана Кобэма и Джека Эдмондса ), утверждает, что вычислительные задачи могут быть реально вычислены на некотором вычислительном устройстве, только если они могут быть вычислены за полиномиальное время ; то есть, если они лежат в классе сложности P . В современных условиях, он определяет сговорчивым проблемы с классом сложности P .

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

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

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

Ограничения

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

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

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

Все три связаны между собой и представляют собой общие претензии к анализу алгоритмов , но они особенно применимы к тезису Кобхэма, поскольку он явно заявляет о практичности. Согласно тезису Кобхэма, задача, для которой лучший алгоритм требует n 200 инструкций, считается выполнимой, а проблема с алгоритмом, который принимает 2 0,00001 n инструкций, - невыполнимой - даже при том, что невозможно решить экземпляр размера n = 2 с помощью первого алгоритма. , в то время как пример последней задачи размера n = 10 6 может быть решен без труда. В областях, где практические задачи имеют миллионы переменных (например, исследование операций или автоматизация проектирования электроники ), даже O ( n 3 ) алгоритмы часто непрактичны.

использованная литература