For i ranging from 1 to 13: if bit i is zero, put integer i into bin A; if bit i is
one, put integer i into bin B. Test the resultant arrangement.
If we don’t have a solution yet, add 1 to the binary number and try again. If
we reach 1111111111111, we will stop and conclude that there is no solution.
This is fairly simply algorithm; the only problem is that it takes O(2
n )
time, that is, “exponential time”. In the above example, we may need to try as
many as 2
13 arrangements. This is fine for all small values of n (such as 13), but
becomes unreasonable for large values of n.
We could find many shortcuts for problems such as this, but the best we
can do is improve the coefficients. The time complexity remains O(2
n ).
Problems that require exponential time are referred to as “Intractable”
problems.
There are many variants to this problem.
• We can have mul ti ple bins.
• We can have a sin gle bin, and the object is to pack as much as pos si ble
into it.
• We can pack objects with mul ti ple dimen sions (vol ume and weight, for
exam ple).
7.5 BOOLEAN SATISFIABILITY
Assume we have n Boolean variables, viz., A, B, C, .... and an expression in the
propositional Calculus i.e., we can use and, or and not to form the expression.
Is there an assignment of truth values to the variables, (for example, A = true,
B = true, C = false), that will make the expression true?
Here is a nondeterministic algorithm to solve the problem: For each
Boolean variable, assign if the proper truth value. This is a linear algorithm.
We can find a deterministic algorithm for this problem in much the same way
as we did for the integer bin problem. Effectively, the idea is to set up a
systematic procedure to try every possible assignment of truth values to
variables. The algorithm terminates when a satisfactory solution is found, or
when all 2
n possible assignments have been tried. Again, the deterministic
solution requires exponential time.
Ì Exam ple 7.5.1: Check whether the boolean formula
∅ = ∧ ∨ ∧
(
) (
)
x y
x z
is satisfiable or not.
Solu tion
A Boolean formula is satisfiable if some assignment of 0s and 1s to the
variables makes the formula evaluate to 1.
When x = 0, y = 1 and z = 0, we have
238
Theory of Automata, Formal Languages and Computation
one, put integer i into bin B. Test the resultant arrangement.
If we don’t have a solution yet, add 1 to the binary number and try again. If
we reach 1111111111111, we will stop and conclude that there is no solution.
This is fairly simply algorithm; the only problem is that it takes O(2
n )
time, that is, “exponential time”. In the above example, we may need to try as
many as 2
13 arrangements. This is fine for all small values of n (such as 13), but
becomes unreasonable for large values of n.
We could find many shortcuts for problems such as this, but the best we
can do is improve the coefficients. The time complexity remains O(2
n ).
Problems that require exponential time are referred to as “Intractable”
problems.
There are many variants to this problem.
• We can have mul ti ple bins.
• We can have a sin gle bin, and the object is to pack as much as pos si ble
into it.
• We can pack objects with mul ti ple dimen sions (vol ume and weight, for
exam ple).
7.5 BOOLEAN SATISFIABILITY
Assume we have n Boolean variables, viz., A, B, C, .... and an expression in the
propositional Calculus i.e., we can use and, or and not to form the expression.
Is there an assignment of truth values to the variables, (for example, A = true,
B = true, C = false), that will make the expression true?
Here is a nondeterministic algorithm to solve the problem: For each
Boolean variable, assign if the proper truth value. This is a linear algorithm.
We can find a deterministic algorithm for this problem in much the same way
as we did for the integer bin problem. Effectively, the idea is to set up a
systematic procedure to try every possible assignment of truth values to
variables. The algorithm terminates when a satisfactory solution is found, or
when all 2
n possible assignments have been tried. Again, the deterministic
solution requires exponential time.
Ì Exam ple 7.5.1: Check whether the boolean formula
∅ = ∧ ∨ ∧
(
) (
)
x y
x z
is satisfiable or not.
Solu tion
A Boolean formula is satisfiable if some assignment of 0s and 1s to the
variables makes the formula evaluate to 1.
When x = 0, y = 1 and z = 0, we have
238
Theory of Automata, Formal Languages and Computation