hipoteza P ≠ NP
 
Encyklopedia PWN
hipoteza P ≠ NP,
mat. hipoteza w teorii złożoności obliczeniowej stwierdzająca, że klasa problemów rozwiązywanych przez deterministyczne maszyny Turinga w czasie zależnym wielomianowo od rozmiaru wejścia (P) jest różna (dokładniej — mniejsza) od analogicznej klasy dla maszyn niedeterministycznych (NP);
z h. P ≠ NP wynika, że wiele ważnych problemów nie może być w praktyce rozwiązywanych z pełną dokładnością przez komputer, z uwagi na zbyt długi czas oczekiwania na wynik.
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia