Feasibilism, Explication, and the Cobham-Edmonds Thesis
For theoretical computer scientists, this paper critically evaluates the foundational assumption that P captures feasible computation, but its arguments are largely philosophical and do not provide new empirical or mathematical results.
This paper examines the Cobham-Edmonds thesis, which equates feasible computation with polynomial-time complexity class P, and presents arguments analogous to those supporting the Church-Turing thesis. It finds that existing arguments for the thesis are based on utility rather than necessity.
While the Church-Turing thesis asserts that effective calculability explicates to sets decidable by a Turing machine, the Cobham-Edmonds thesis asserts that feasible computation explicates to the complexity class $\mathsf{P}$, those decidable by a polynomial-time bounded Turing machine. The Church-Turing thesis has been placed under rigorous scrutiny and has several convincing arguments in its favor, but the Cobham-Edmonds thesis has not undergone a similar examination. Many of the arguments in its favor simply suggest that $\mathsf{P}$ is a useful assumption, rather than a necessary target. This paper presents analogous arguments in favor of the Cobham-Edmonds thesis.