O(n^2) 以上の漸近下限が証明されている P の問題はありますか? (n は、問題インスタンスを表すことができるビット数です)。これは宿題の質問ではなく、ただの好奇心です。
2 に答える
6
はい、時間階層定理はそのような問題の存在を意味します。すべての O(n^2) 時間アルゴリズムで対角化する必要があるため、間違いなく自然ではありません。
于 2013-06-22T19:12:31.207 に答える
2
3SUMが思い浮かびます。Jeff Erickson による、特定の線形決定木モデルで知られている 2 次下限があります。(さまざまな計算モデルの文献には、3SUM のギリギリ準二次アルゴリズムがいくつかあります。しかし、私はそれらを見たことがないので、それらがどのように機能するのかわかりません。)
于 2013-06-23T08:35:23.653 に答える