一些算法問題的可證明下界？
有沒有我們知道下界的問題？
例如，對於基於比較的排序，我們知道您需要 $ \Omega(n \log n) $ 比較。 *編輯：*我知道這需要將算法限制為比較。我想不出無限制模型中的任何下限，但我最感興趣的是無限制計算的下限。
我這樣做的動機是：雖然我們不知道如何證明單向函式存在，但也許我們不需要它來至少在評估函式和反轉函式之間實現一些可證明的多項式分離。甚至有問題 $ \Omega(n^7) $ 足以建立一些實用的密碼學： $ c \cdot (2^{128})^{\frac{1}{7}} \approx c\cdot319557 $ 位（對於一些常數 $ c $ ) 將需要獲得與 128 位密鑰相同的安全級別。
這個問題有意義嗎？如果沒有，我哪裡錯了？我的計算有意義嗎？
也許我們不需要它來在評估函式和反轉它之間至少實現一些可證明的多項式分離。甚至有問題 $ \Omega(n^7) $ 足以建立一些實用的密碼學： $ c⋅(2128)17≈c⋅319557 $ 位（對於一些常數 $ c $ ) 將需要獲得與 128 位密鑰相同的安全級別。
有些人嘗試過思考這個問題。相關名稱是“細粒度密碼學”。你可以展示你所暗示的東西——誠實方與敵對方的複雜性中的一些多項式“差距”。Ralph Merkle 的早期密碼系統之一（“Merkle Puzzles”）實際上就是這種形式。它可以說是最早的公開（我相信 GCHQ 有一些東西）公鑰密碼系統，但只是在上述“細粒度”的意義上。在這裡，您仍然需要做出一些困難假設——特別是您需要一個隨機預言機。但是你從一個隨機的預言機中獲得了公鑰加密，儘管只有多項式計算間隙。
如果您對更弱的加密也滿意，您可以刪除額外的假設以獲得“完全可證明”的結果。特別是，您可以獲得諸如“存在一個電路，可在 $ AC^0 $ ，其逆不是”（因此 OWF 為 $ AC^0 $ ）。參考這篇論文的介紹。
例如，對於基於比較的排序，我們知道您需要 $ \Omega(n \log n) $ 比較。
這是一個很好的例子，因為它是我們知道如何證明的下界的例子。一般來說，我們只知道
$$ 1 $$如何證明受限計算模型的下界。範例包括：
- 問題的決策樹複雜度（ $ \Omega(n \log n) $ 排序比較的下限是這種形式）
- 問題的通信複雜性（我之前在密碼學的時間/空間權衡論文中看到過這一點）
- 通用組模型中的下限
當然還有其他適用於密碼學的下限（例如，我正在進行使用一些球形包裝下限的工作），但它們更加專業。
$$ 1 $$人們可以證明在圖靈機計算模型中被推測為困難的特定問題的下界，但它們非常弱。特別是，我認為我們在 3-SAT 上的最佳下限只是線性的（常數為 $ 4 $ 或者其他的東西）。