hipoteza P ≠ NP

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.