計算決策性問題的一種性質(zhì)，指在非確定性杜林機求解決策性問題，其求解所需的步驟和輸入資料的大小成多項式函數(shù)的關(guān)系者。非確定性的意思為產(chǎn)生該問題所有的可能解，再以試誤法一一檢驗。雖然檢驗一可能解可在多項式時間完成，但整個檢驗可能需用指數(shù)時間才能完成工作。參【決策問題】（decision problem）。
