Cobham Tezi
Gelen bilgisayar bilimleri , Cobham tezi olarak da bilinen, Cobham - Edmonds tezi (adını Alan Cobham ve Jack Edmonds ), postülatları o "kolayca" hesaplanabilir sorunlar polinom zaman hesaplanabilir sorunlardır. Özellikle "kolayca" hesaplanabilen karar problemleri P sınıfına aittir .
Alan Cobham'ın (1965) makalesi, fonksiyonların içsel hesaplama zorluğu olarak adlandırılır ve P sınıfının ilk oluşumlarından biridir .
Bu tez önemlidir, çünkü P sınıfı kesinlikle bir hesaplama modelinin ayrıntılarına duyarlı olmayan bir sınıftır: örneğin, bir bantlı veya birkaç bantlı bir Turing makinesi, P sınıfının aynı tanımını verir.
Bu tez, polinomun üssünü hiç hesaba katmadığı için eleştirildi, ancak deterministik zaman hiyerarşi teoremine göre , en iyi algoritmanın keyfi olarak büyük bir üssüne sahip olduğu problemler var.
Notlar ve referanslar
-
D. Pisinger, 2003. "Zor sırt çantası sorunları nerede?" Teknik Rapor 2003/08, Bilgisayar Bilimleri Bölümü, Kopenhag Üniversitesi, Kopenhag, Danimarka, bkz. [1] , 31 Ocak 2015'te erişildi.
-
(inç) Oded Goldreich , Hesaplamalı karmaşıklık: kavramsal bir bakış açısı , Cambridge, Cambridge University Press ,
2008, 606 s. ( ISBN 978-0-521-88473-0 , çevrimiçi okuyun ) , s. 128
-
(inç) Dexter Kozen , Hesaplama Teorisi , Londra, Birkhauser,
2006, 418 s. ( ISBN 978-1-84628-297-3 , çevrimiçi okuyun ) , s. 4
-
(in) Egon BOERGER ( trans. Almanca itibaren), Hesaplanabilirlik, karmaşıklık, mantık , Amsterdam / New York / New York, NY, ABD, Elsevier ,
1989( ISBN 978-0-444-87406-1 , çevrimiçi okuyun ) , s. 225.
-
Steven Homer ve Alan L. Selman, “Karmaşıklık Teorisi,” içinde Bilgisayar Bilimi ve Teknolojisi Ansiklopedisi , vol. 26, CRC Basın,
1992( çevrimiçi okuyun )
-
Alan Cobham , "Fonksiyonların içsel hesaplama zorluğu" , Proc. Mantık, Metodoloji ve Bilim Felsefesi II , Kuzey Hollanda,
1965