在計算機科學中，決策問題的屬性測試算法是一種算法，其對其輸入的查詢復雜度遠遠小于問題的實例大小。典型的屬性檢驗算法是用來區分某些組合結構S（如圖或布爾函數）是否滿足某種屬性P，或者是否離這種屬性很遠（意味著需要修改S的表征的ε部分以使S滿足P），只需使用對該對象的少量局部查詢。例如，下面的承諾問題有一個算法，其查詢復雜度與實例大小無關（對于一個任意的常數ε>0）。給定一個有n個頂點的圖G，決定G是否是雙聯的，或者即使除去一個任意的子集，G也不能成為雙聯的，最多屬性檢驗算法是概率可檢驗證明定義的核心，因為概率可檢驗證明本質上是一個可以被屬性檢驗算法驗證的證明。

形式上，對于一個決策問題L，具有查詢復雜度q(n)和接近性參數ε的屬性檢驗算法是一種隨機算法，在輸入x（L的一個實例）時，對x最多進行q(|x|)查詢，其行為如下。如果x在L中，該算法以至少?的概率接受x；如果x離L有ε-far，該算法以至少?的概率拒絕x。這里，x離L有ε-far意味著x與L中任何字符串的漢明距離至少為ε|x|。如果一個屬性檢驗算法滿足更強的條件，即實例x∈L的接受概率是1而不是?，則稱該算法具有單邊錯誤。如果一個屬性檢驗算法在觀察到以前的查詢的任何答案之前就執行了所有的查詢，則被稱為非自適應算法。這樣的算法可以被看作是以下列方式運行的。首先，該算法接收其輸入。在查看輸入之前，利用其內部隨機性，算法決定輸入的哪些符號要被查詢。接下來，該算法觀察這些符號。最后，在不進行任何額外查詢（但可能使用其隨機性）的情況下，該算法決定是否接受或拒絕輸入。

一個屬性測試算法的主要效率參數是它的查詢復雜度，它是在給定長度的所有輸入（以及算法做出的所有隨機選擇）上檢查的xxx輸入符號數。人們對設計其查詢復雜度盡可能小的算法感興趣。在許多情況下，屬性檢測算法的運行時間是實例長度的亞線性。通常情況下，我們的目標是首先使查詢復雜度作為實例大小n的函數盡可能小，然后研究對接近度參數ε的依賴性。與其他復雜度理論設置不同，屬性測試算法的漸進查詢復雜度受到實例表示法的極大影響。例如，當ε=0.01時，測試密集圖（由其鄰接矩陣表示）的二分性的問題就有一個恒定查詢復雜度的算法。相反，n個頂點的稀疏圖（由其鄰接列表表示）需要查詢復雜度的屬性測試算法對于所有非瑣碎的屬性，屬性測試算法的查詢復雜度會隨著接近度參數ε的變小而增長。

這種對ε的依賴是必要的，因為輸入中少于ε的符號的變化不能用少于O(1/ε)的查詢來以恒定的概率檢測。密集圖的許多有趣的屬性可以用查詢復雜度來測試，而查詢復雜度只取決于ε，而不取決于圖的大小n。例如，在很長一段時間內，測試圖是否不包含任何三角形的最佳算法的查詢復雜度是poly(1/ε)的塔函數，直到2010年才改進為log(1/ε)的塔函數。這種界限的巨大增長的原因之一是，許多關于圖的屬性檢驗的積極結果是利用Szemerédi正則性定理建立的，該定理的結論中也有塔式界限。