Вопросы с тегом «boolean-formulas»

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

Я изучаю проблему, которая трудна для класса количественных логических формул с логарифмическим числом чередований кванторов. Проблема в этом классе будет выглядеть так: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalog⁡n−1,…xaжурнал⁡N)F\forall (x_1, x_2, \ldots...

Рассмотрим следующую проблему решения Входные данные : монотонный CNF ΦΦ\Phi и монотонный DNF ΨΨ\Psi . Вопрос : Φ→ΨΦ→Ψ\Phi \to \Psi тавтология? Определенно вы можете решить эту проблему в O(2n⋅poly(l))O(2n⋅poly(l))O(2^n \cdot \mathrm{poly}(l)) -time, где nnn - количество переменных в Φ→ΨΦ→Ψ\Phi \to...

Дерево решений однократного чтения определяется следующим образом: и F L сек е считываются однократно деревьев решений.Tг у йTrueTrueFл ы еFalseFalse Если и B являются деревьями решений с однократным чтением, а x является переменной, не встречающейся в A и B , то ( x ∧ A ) ∨ ( ˉ x ∧ B ) также...

Я ищу ссылки на сложность проблемы балансировки булевых формул . В частности, Было ли известно, что булевы формулы могут быть сбалансированы в ?AC0AC0\mathsf{AC^0} Есть ли простое доказательство балансировки булевой формулы в ?AC0AC0\mathsf{AC^0} Под «простым» я подразумеваю доказательство, более...