2
Czy istnieją problemy „pełne (O)”?
Wiele klas złożoności ma „kompletne” problemy. Czy istnieją kompletne problemy dla klasy złożoności problemów, które można rozwiązaćO ( 1 )O(1)O(1) czas? Komplikacja polega na tym, że klasa ta zależy od modelu obliczeniowego; problem można rozwiązaćO ( 1 )O(1)O(1)czas w jednym rozsądnym modelu obliczeniowym, ale nie w innym, biorąc pod uwagę, …