【非決定性多項式定時】

豐碩

【非決定性多項式定時】

 

英語翻譯：nondeterministicpolynomialtime

 

【辭書名稱】資訊與通信術語辭典

 

計算決策性問題的一種性質，指在非確定性杜林機求解決策性問題，其求解所需的步驟和輸入資料的大小成多項式函數的關係者。

 

非確定性的意思為產生該問題所有的可能解，再以試誤法一一檢驗。

 

雖然檢驗一可能解可在多項式時間完成，但整個檢驗可能需用指數時間才能完成工作。

 

參【決策問題】（decisionproblem）。

 

 

轉自:http://edic.nict.gov.tw/cgi-bin/tudic/gsweb.cgi?o=ddictionary