Введение
Тезис, утверждающий, что вычислительные задачи могут быть эффективно решены только за полиномиальное время.
Тезис Кобэма, также известный как тезис Кобэма — Эдмондса (названный в честь Алана Кобэма и Джека Эдмондса), утверждает, что вычислительные задачи могут быть эффективно решены на некотором вычислительном устройстве только в том случае, если они могут быть решены за полиномиальное время, то есть, если они принадлежат классу сложности P. В современных терминах, он отождествляет разрешимые задачи с классом сложности P.
Формально, говорить о том, что задача может быть решена за полиномиальное время, означает, что существует алгоритм, который, получив на вход экземпляр задачи размером n бит, может найти решение за время O(nc), используя нотацию «большое O», где c — константа, зависящая от задачи, но не от конкретного экземпляра. Статья Алана Кобэма 1965 года под названием «Внутренняя вычислительная сложность функций» является одним из первых упоминаний о концепции класса сложности P, состоящего из задач, разрешимых за полиномиальное время. Кобэм предположил, что этот класс сложности является хорошим способом описать множество эффективно вычислимых задач. Статья Джека Эдмондса 1965 года «Пути, деревья и цветы» также признаётся за отождествление P с разрешимыми задачами.
Ограничения
Хотя тезис Кобэма является важной вехой в развитии теории вычислительной сложности, он имеет ограничения применительно к практической реализуемости алгоритмов. Суть тезиса заключается в том, что "P" означает "легко, быстро и практично", а "не в P" – "трудно, медленно и непрактично". Однако это не всегда верно, поскольку тезис абстрагируется от важных переменных, влияющих на время выполнения на практике: он игнорирует постоянные факторы и члены низшей степени, размер показателя степени. Теорема об иерархии времени доказывает существование задач в P, требующих произвольно больших показателей. Он также игнорирует типичный размер входных данных. Все три аспекта взаимосвязаны и являются общими замечаниями к анализу алгоритмов, но они особенно актуальны для тезиса Кобэма, поскольку он содержит прямое утверждение о практичности. Согласно тезису Кобэма, задача, для которой лучший алгоритм требует n<sup>200</sup> инструкций, считается решаемой, а задача с алгоритмом, требующим 20.00001n инструкций – нерешаемой, даже если экземпляр размера n = 2 невозможно решить первым алгоритмом, в то время как экземпляр последней задачи размера n = 10<sup>6</sup> можно решить без затруднений. В областях, где практические задачи содержат миллионы переменных (например, исследование операций или автоматизация проектирования электронных схем), даже алгоритмы со сложностью O(n<sup>3</sup>) часто оказываются непрактичными. Кроме того, во многих случаях достаточно приблизительных решений, если точное решение найти невозможно. Например, задача коммивояжера, как считается, не имеет точного полиномиального решения (является NP-трудной), но хорошие решения могут быть получены за полиномиальное время с использованием таких методов, как алгоритм Кристофидеса.
It ignores constant factors and lower order terms. It ignores the size of the exponent. The time hierarchy theorem proves the existence of problems in P requiring arbitrarily large exponents. It ignores the typical size of the input. All three are related and are general complaints about analysis of algorithms, but they particularly apply to Cobham's thesis, since it makes an explicit claim about practicality. Under Cobham's thesis, a problem for which the best algorithm takes n200 instructions is considered feasible, and a problem with an algorithm that takes 20.00001 n instructions infeasible—even though one could never solve an instance of size n = 2 with the former algorithm, whereas an instance of the latter problem of size n = 106 could be solved without difficulty. In fields where practical problems have millions of variables (such as operations research or electronic design automation), even O(n3) algorithms are often impractical. A separate consideration is that in many cases, one is often content with approximate solutions if an exact solution cannot be found. For example, the travelling salesman problem is widely suspected to be unsolvable exactly in polynomial time (it is NP hard), but good solutions can be obtained in polynomial time with methods such as the Christofides algorithm.