비결정적 알고리즘

비결정론적 알고리즘(영어: Nondeterministic algorithm)은 결정론적 알고리즘과는 달리, 동일한 입력이 주어지더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 의미한다.

f(n) 개의 단계를 수행하는 결정론적 알고리즘은 언제나 f(n) 개의 단계를 수행하며 언제나 같은 결과를 도출한다. f(n) 개 높이의 단계를 수행하는 비결정론적 알고리즘은 수행할 때마다 다른 과정을 거쳐서, 언제나 같은 결과를 도출하지 않을 수 있다. 비결정론적 알고리즘은 수행도의 높이는 고정되어 있더라도 그 크기는 무한할 수 있기 때문에 영원히 끝나지 않을 수도 있다.

참고 문서

• 비결정론적 튜링 기계
• 비결정론적 프로그래밍(:en:Nondeterministic programming)

같이 보기

• 비결정론적 튜링 기계