2008-08-31から1日間の記事一覧
Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas Ryan Williams Quantified boolean formula problem (の一般化)がおよそ n log n 時間の非線型下界を持つ,という結果です.QBF問題自体はPSPACEに入ることしか知られていません…
Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas Ryan Williams Quantified boolean formula problem (の一般化)がおよそ n log n 時間の非線型下界を持つ,という結果です.QBF問題自体はPSPACEに入ることしか知られていません…