Nedeterministický počítač

Nedeterministický počítač je počítač, ktorý sa v každom kroku riešenia úlohy môže vybrať naraz viacerými cestami. Nedeterministickým počítačom je napríklad kvantový počítač. Nedeterministický počítač možno pomocou rekurzie simulovať na deterministickom počítači. Úloha, ktorá by na nedeterministickom počítači bola riešiteľná v polynomiálnom čase sa však môže stať na deterministickom počítači úlohou s nepolynomiálnym časom. Ak by sa v každom kroku úloha vetvila iba na dve vetvy, tak úloha riešiteľná na nedeterministickom počítači v 100 krokoch, by na deterministickom počítači mohla byť v najhoršom prípade riešiteľná v 2100 krokoch.

Pozor! Nepliesť si nedeterministický počítač s nedeterministickým algoritmom. Nedeterministické algoritmy možno použiť aj na deterministických počítačoch a naopak.

Teória zložitosti