[知識] Non-deterministic Algorithm

Def: 
這類演算法在做任何事時，該演算法的下一步可能會有無限多件事可以選擇。 (Permitting more than one choice of next move at some step in a computation) 

1.演算法中每一個步驟的運算無法被唯一定義。

2.能夠執行非決定性演算法的機器，稱為非決定性的機器 (Non-deterministic Machine)。
  2-1 由於非決定性演算法在執行時，每一步可能有無限多件事要處理，故非決定性計算機器需假設有無限多個處理器可平行處理。因此，非決定性計算機器的計算能力比決定性計算機器要強大。
  2-2 但是，實際上並不存在此種機器。

Non-deterministic Algorithm的執行步驟分成兩個階段：
1.猜測階段(Guess)
  由於沒有一個既定的程序來從事此階段的猜測工作，因此本階段是Non-deterministic
  對於本階段，我們只知道一件事：
  1-1 如果一個問題有正確解的話，此階段一定可以將這個正確解給猜出來；反之，若該問題沒有正確解的話，則此階段就會隨便給解答。
  1-2 至於猜測階段是怎麼將這個解答給找出來的，我們無從得知(不論所給的解是否為正確解) 。

2.驗証階段(Verification)
  將上一階段所猜出來的結果加以驗証是否為真 (True)