効率的に解ける

9 の用例 (0.00 秒)
  • そのような問題は、一般的には効率的に解けるとは思われていない。
  • 充足可能性問題は、全ての変数が存在量化された特殊ケースと見ることもでき、存在的様式だけで効率的に解ける。
  • しかし、複雑性理論の様々な近似は、これらの問題のいくつかが効率的に解けることを示唆する。
  • Pはしばしば、「効率的に解ける」問題のクラスとして扱われる。
  • Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。
  • 次の問題が効率的に解けることと、誤差が高々倍の解を出力する多項式時間アルゴリズムが存在することは同値である。
  • 明らかに SL-完全問題が全て L に属することになり、全て決定性の対数領域/多項式領域のアルゴリズムで効率的に解ける可能性が示された。
  • しかしながら、RPやBPPといった乱択で解けるクラスも、Pより大きいかもしれないが「効率的に解ける」と考えることもできる。
  • 歴史的に見れば、1976年にミラー-ラビン素数判定法によって素数判定が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。