The complexity-theoretic Church–Turing thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time.
Den stærke Church-Turing-tese postulerer da, at alle 'rimelige' beregnelighedsmodeller udtrykker den samme klasse af problemer, som kan beregnes i polynomiel tid.