Вычислимость булевой формулы

[dmitryf]

А если дана произвольная булева формула и сертификат в виде значений переменных на которых она выполнима, можно ли это проверить на машине тьюринга без парсинга выражения?

[arseniiv]

Заменяете все имена переменных на их значения, потом заменяете термы вида $a*b$, где $a,b\in\{0,1\}$ и $*$ — операция, их значениями, пока возможно. Когда осталось одно значение, проверка его на совпадение с $1$. Но это легко, если скобки везде расставлены — а если нет…

А откуда такая странная задача?

-- Чт окт 15, 2015 03:38:30 --

P. S. Ну и $\neg a$ тоже заменяете, конечно.

[dmitryf]

Согласен, со скобками легко, без скобок еще придется на приоритет смотреть. Это я на лекции услышал, что можно как-то проще выполнимость проверить не разбирая выражение, но вспомнить не могу, может там и рассматривался случай со скобками.

Я теперь для смежной задачи, вычислимости алгебраического выражения, не могу понять следующую вещь, а как доказать, что всегда найдется выполнимый набор, длина которого ограничена полиномом от длины выражения? То есть, что если выражение выполнимо, то обязательно найдутся маленькие X для этого. Если нет свободных коэффициентов, то понятно, можно значения X просто поделить нужное количество раз. А если есть?

Задача выяснения, является ли алгебраическое выражение (с целыми коэффициентами, знаками сложения и умножения, и скобками) не тождественно нулевым (то есть, принимающим ненулевое значение при некоторых действительных значениях переменных).