Временная сложность сб

Question

Как именно измеряется сложность решателя SAT? для N переменных вы можете иметь. например, (A∧B) ∨ (A∧B), тогда максимальный размер формулы не ограничен. В этом случае, не будет ли сложность лучше измерять с точки зрения сложности формулы, а не сколько переменных она занимает?

Answer 1

Количество переменных является подходящей мерой сложности проблемы. Каждая из N переменных может принимать значение true или false, поэтому возможны 2 ^N возможных входов. SAT-решатель просто должен проверить, может ли он найти какую-либо комбинацию значений для входных данных, чтобы уравнение (выражение) давало 'true'.