Nedeterministický polynomiálny problém

Nederministický polynomiálny problém je taký problém (taká úloha), ktorý je riešiteľný v polynomiálnom čase na nedeterministickom počítači.

Teória zložitosti