-1
私が考えているように、回路と数式（式）は同じブール値の2つの異なる表現でなければならず、big-Oはちょうどnでなければなりません。しかし、誰かが1対1で対応していないと言ったのはなぜですか？ブール回路をブール式に変換するための基本的なアルゴリズムとは何ですか？複雑さは何ですか？
A
答えて
2
ブール回路は任意の非周期グラフに基づいていますが、論理式はツリーとして記述できます。したがって、ブール回路はサブ回路を一度評価し、その結果を複数の場所で使用することができますが、明らかに同じサブツリーのコピーが表示される単一の数式としてこれを書き出そうとすると複数の場所では、指数関数的にツリーのサイズを爆破することができます。
あなたは、私はちょうど追加する必要がhttps://en.wikipedia.org/wiki/Tseytin_transformation
関連する問題
- 1. 関連するコンテンツクエリの基本的なアルゴリズムは何ですか？
- 2. テキストマイニングの基本的なアルゴリズムは何ですか？
- 3. 真の違いは何ですか？ブール
- 4. JNI - 基本Javaオブジェクト（ブール値）を表すjobjectをネイティブの基本型（ブール値）に変換する
- 5. コンパイラの基本型の自動型変換のための良いアルゴリズムとは何ですか？
- 6. このアルゴリズムの時間の複雑さは何ですか
- 7. このアルゴリズムの複雑さは何ですか
- 8. パスカル・トライアングル・アルゴリズムの時間複雑さは何ですか？
- 9. 2Dでポリゴンモデルを回転させるための基本的なアイデアは何ですか？
- 10. モデルをトレーニングするための基本的なステップは何ですか？
- 11. ブール値のコンテキストで使用すると、オブジェクトをブール値に変換したいのはなぜですか？
- 12. GroupBy操作の漸近的な複雑さは何ですか？
- 13. List.Addの漸近的な複雑さは何ですか？
- 14. .inoファイルを.hexに変換するアルゴリズムとは何ですか？
- 15. dist（）の複雑さは何ですか？
- 16. ブールは何ですか？ isActive = falseはC＃で意味ですか？
- 17. DICOMでブール値に最も適した値は何ですか？
- 18. setとdidSetの基本的な違いは何ですか？
- 19. 基本的なC＃インターフェイスのスコープとは何ですか？
- 20. ToString（）とConvert.ToString（）の基本的な違いは何ですか？
- 21. jobconfとjobの基本的な違いは何ですか？
- 22. アンドロイドプログラミングのための最も基本的なツールチェーンは何ですか？
- 23. 再帰アルゴリズムの空間複雑性を見つける一般的な方法は何ですか？時間の複雑さを見つけるために
- 24. このbash whileループのブール式では、-ltの意味は何ですか？
- 25. ブール値を返すメソッドとは何ですか？
- 26. このアルゴリズムでは「基本操作」は正確に何か
- 27. 明示的なブール変換
- 28. 写真を現実的なアバターにするための基本的な手順は何ですか？
- 29. ブール式アルゴリズムの簡略化
- 30. ブール式から余分なカッコを削除するアルゴリズム
を使用して変数の数を増やすのコストで、このブローアップを回避することができます：単一式しか組み合わせ論理回路を意味していますが、回路の表現を得た場合は除外することはできません任意の複雑さおよび挙動を有する順序論理回路（メモリまたはループを有する）である。 – Spektre