區分多項式和洛朗多項式
讓 $ f(x) \in \mathbb{Z}p[x] $ （對於素數 $ p \gg d $ ) 是一次多項式 $ d $ ， 然後讓 $ g(x) $ 是具有相同次數且只有第一個負指數項的 Laurent 多項式 ( $ g(x) = \frac{a{-1}}{x} + a_0 + a_1 x + \dots a_dx^d $ ) 在同一領域。
現在，假設我們獲得了對這兩個函式的 oracle 訪問權限，附加條件是我們只能 $ < d $ 查詢（否則我們可以問 $ d+1 $ 查詢並插入點以檢查函式是否為多項式 - 這是我能想到的唯一方法。）
這可能嗎 - 如果測試不必是完美的並且可能有一些誤報或負數？
這可能嗎
除非查詢 $ g(0) $ 為 Laurent 多項式提供可區分的錯誤，並假設值 $ a_0, …, a_d $ 是等分佈的（對於 Laurent 和正態多項式情況），如果您僅限於 $ d $ 查詢。
這個問題等同於問“您被授予 Oracle 訪問 Laurent 多項式的權限 $ g(x) = \frac{a_{-1}}{x} + a_0 + a_1 x + \dots a_dx^d $ , 你能確定是否 $ a_{-1} = 0 $ ？”
$$ 1 $$ 那麼，對於任何固定值 $ a_{-1} $ ， 這 $ d $ 查詢可能導致任何 $ p^d $ 具有相等機率的可能響應集（因為存在唯一的多項式 $ a_0 + a_1 x + \dots a_dx^d $ 這導致 $ d $ 必需的 $ g(x) - \frac{a_{-1}}{x} $ 值）。因為這對於任何值都是正確的 $ a_{-1} $ ，我們無法獲得任何關於它的值的資訊（包括它是否為0）。
$$ 1 $$: 隨著約定 $ \frac{0}{0} = 0 $