Portal:Algorytmy/Ciekawostki

Czy wiesz, że...

• różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność?
• maszyna posiadająca zdolność wykonywania dowolnego programu jest nazywana uniwersalną Maszyną Turinga, a praktyczną realizacją uniwersalnej Maszyny Turinga jest komputer?
• zgodnie z twierdzeniem Weierstrassa dowolną funkcję ciągłą na przedziale zamkniętym można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia?