context: But bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" (Goldreich 2008, Chapter 1.2). This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.
question: ఒక కంప్యూటేషనల్ మోడల్లో సమయ సంక్లిష్టతలలో ఒక బహుపద సంబంధం ఉందని ఏ సిద్ధాంతం సూచిస్తుంది?
answers: Cobham-Edmonds thesis Cobham-Edmonds Cobham-Edmonds thesis