Teza Edmondsa
Teza Edmondsa, znana również jako teza Cobhama-Edmondsa (od Alana Cobhama i Jacka Edmondsa)[1][2], stwierdza, że dany problem obliczeniowy jest praktycznie obliczalny przez jakieś urządzenie obliczeniowe wtedy i tylko wtedy, gdy istnieje algorytm obliczający go w czasie wielomianowym; to znaczy, gdy problem ten leży w zasięgu klasy złożoności P[3].
Formalnie, powiedzieć, że problem można rozwiązać w czasie wielomianowym znaczy, że istnieje algorytm, który, przyjmując n-bitową instancję problemu na wejściu, zwraca rozwiązanie w czasie O(nc), gdzie c jest stałą, zależną od typu problemu (ale nie od jego konkretnej instancji)[4].
Jack Edmonds był jednym z twórców dziedziny optymalizacji kombinatorycznej. Jego artykuł z 1965 roku zatytułowany "Paths, trees, and flowers"[1] był jednym z pierwszych dokumentów sugerujących możliwość ustanowienia matematycznej teorii efektywnych algorytmów kombinatorycznych. W artykule tym Edmonds postawił również tezę, jakoby klasa złożoności P stanowiła dobrą reprezentację zbioru problemów praktycznie obliczalnych.
Przypisy edytuj
- ↑ a b Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467. doi:10.4153/CJM-1965-0454.
- ↑ Cobham, Alan (1965). “The intrinsic computational difficulty of functions”, in Yehoshua Bar-Hillel (ed.), Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress (Studies in Logic and the Foundations of Mathematics). North-Holland Publishing 24-30. doi: 10.2307/2270886.
- ↑ Homer, Steven and Selman, Alan (1992). "Complexity Theory", in Alan Kent and James G. Williams, Encyclopedia of Computer Science and Technology, 26, CRC Press.
- ↑ Jones, Neil .D (1997). „Computability and Complexity From a Programming Perspective”. The MIT Press, Cambridge, London.