Nedeterministický počítač
 |
Tomuto článku alebo sekcii chýbajú odkazy na spoľahlivé zdroje, môže preto obsahovať informácie, ktoré je potrebné ešte overiť. Pomôžte Wikipédii a doplňte do článku citácie, odkazy na spoľahlivé zdroje. |
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.
|
Tento článok týkajúci sa počítačov je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš. |