Cobham's Thesis as the Sorites Paradox

Abstract

According to Cobham’s thesis, computational problems can be practically (or, in other words, feasibly) computed on some computational device only if they can be computed in polynomial time. Despite the presence of many objections to this claim, they are all not decisive. Then again, there is one not explored yet critical objection to the claim. Namely, Cobham's thesis is susceptible to paradoxical reasoning emerging as a result of the indeterminacy surrounding limits of application of the vague predicate “is practical” (“is feasible”). What is more, as it is demonstrated in the present paper, any attempt to defuse such reasoning and make Cobham's thesis non paradoxical causes it to become of no purpose at all.