Кіріспе
Есептеу мәселелерін тек полиномиялық уақытта ғана тиімді есептеуге болады деген тезис – Кобхамның тезисі, сондай-ақ Кобхам-Эдмондс тезисі (Алан Кобхам мен Джек Эдмондс есімдерімен аталған) есептеу мәселелерін кейбір есептеу құрылғысында тек полиномиялық уақытта есептеуге болады деп тұжырымдайды; яғни, егер олар күрделілік класы P-ге жатса. Қазіргі терминдермен айтқанда, ол P күрделілік класымен байланысты тиімді шешілетін мәселелерді анықтайды.
Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. In modern terms, it identifies tractable problems with the complexity class P.
Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n bit instance of the problem as input, can produce a solution in time O(nc), using the big O notation and with c being a constant that depends on the problem but not the particular instance of the problem. Alan Cobham's 1965 paper entitled "The intrinsic computational difficulty of functions" is one of the earliest mentions of the concept of the complexity class P, consisting of problems decidable in polynomial time. Cobham theorized that this complexity class was a good way to describe the set of feasibly computable problems. Jack Edmonds's 1965 paper "Paths, trees, and flowers" is also credited with identifying P with tractable problems.
Формальды түрде, мәселені полиномиялық уақытта шешуге болады деу, мәселенің n биттік кіріс ретінде берілгенде O(nc) уақытында шешім беретін алгоритмнің бар екенін білдіреді, мұндағы O – үлкен O нотациясы, ал c – мәселенің нақты мысалына емес, мәселеге байланысты тұрақты шама. Алан Кобхамның 1965 жылғы «Функциялардың ішкі есептеу қиындығы» атты жұмысы – полиномиялық уақытта шешілетін мәселелерден тұратын P күрделілік класы тұжырымының алғашқы айтылғандарының бірі. Кобхам бұл күрделілік класының тиімді есептелетін мәселелер жиынтығын сипаттауға жарамды тәсіл деп санайтын. Джек Эдмондстың 1965 жылғы «Жолдар, ағаштар және гүлдер» атты жұмысы да P күрделілік класын тиімді шешілетін мәселелермен теңестіргені үшін ескеріледі.
Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. In modern terms, it identifies tractable problems with the complexity class P.
Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n bit instance of the problem as input, can produce a solution in time O(nc), using the big O notation and with c being a constant that depends on the problem but not the particular instance of the problem. Alan Cobham's 1965 paper entitled "The intrinsic computational difficulty of functions" is one of the earliest mentions of the concept of the complexity class P, consisting of problems decidable in polynomial time. Cobham theorized that this complexity class was a good way to describe the set of feasibly computable problems. Jack Edmonds's 1965 paper "Paths, trees, and flowers" is also credited with identifying P with tractable problems.
Шектеулер
Кобхамның тезисі есептеу күрделілігі теориясының дамуындағы маңызды кезең болса да, алгоритмдердің практикалық қолданылуында шектеулі. Тезис негізінен "P" дегеніміз "оңай, жылдам және практикалық", ал "P-ге жатпайтын" – "қиын, баяу және практикалық емес" дегенді білдіреді деп тұжырымдайды. Бірақ бұл әрқашан рас емес, себебі тезис іс жүзінде орындалу уақытына әсер ететін маңызды айнымалыларды ескермейді: ол тұрақты коэффициенттер мен төменгі дәрежелі мүшелерді назарға алмайды. Ол көрсеткіштің мөлшерін елемейді. Уақыт иерархиясы теоремасы P класында кез келген үлкен көрсеткіштерді қажет ететін мәселелердің бар екенін дәлелдейді. Ол кірістің әдеттегі мөлшерін де ескермейді. Бұл үш фактор да бір-бірімен байланысты және алгоритмдерді талдауға қатысты жалпы шағымдар, бірақ олар Кобхамның тезисіне ерекше қатысты, өйткені ол практикалық жағдайлар туралы нақты мәлімдеме жасайды. Кобхамның тезисіне сәйкес, ең жақсы алгоритмі n200 нұсқаудан тұратын мәселе орындалуға мүмкін деп есептеледі, ал 20.00001n нұсқаудан тұратын алгоритммен шешілетін мәселе орындалмайды, тіпті егер бірінші алгоритммен n=2 өлшемді мәселені шеше алмасаңыз, ал екіншісі n=106 өлшемді мәселені қиындықсыз шеше алады. Практикалық мәселелерде миллиондаған айнымалылары бар салаларда (мысалы, операциялық зерттеулер немесе электрондық дизайнды автоматтандыру) тіпті O(n3) алгоритмдері де жиі практикалық емес. Басқа бір мәселе – көп жағдайда, егер дәл шешім табу мүмкін болмаса, жуық шешімдерге көңілу бөлгені жөн. Мысалы, саяхатшы сатушысының мәселесі полиномиалдық уақытта дәл шешілмейтін деп күдіктенеді (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.