1. Suppose you are given a set of n numbers x 1 , x 2 ,…, x n and are asked to
determine whether this set contains any duplicates.
(a) Suggest an algorithm and find an order-of-magnitude expression for its
time-complexity.
(b) Examine if the implementation of the algorithm on a Turing machine
affects your conclusions.
2. Repeat Exercise 1, this time determining if the set contains any triplicates. Is
the algorithm as efficient as possible?
3. Review how the choice of algorithm affects the efficiency of sorting. What is
the time complexity of the most efficient sorting algorithms?
14.2 Turing Machine Models and Complexity
In the study of computability it makes little difference what particular model of
Turing machine we use, but we have already seen that the efficiency of a
computation can be affected by the number of tapes of the machine and by
whether it is deterministic or nondeterministic. As Example 12.8 shows,
nondeterministic solutions are often much more efficient than deterministic
alternatives. The next example illustrates this even more clearly.
Example 14.2
We now introduce the satisfiability problem (SAT), which plays an important
role in complexity theory.
A logic or boolean constant or variable is one that can take on exactly two
values, true or false, which we will denote by 1 and 0, respectively. Boolean
operators are used to combine boolean constants and variables into boolean
expressions. The simplest boolean operators are or, denoted by V and defined by
0∨1 = 1∨0 = 1∨1 = 1,
0∨0 = 0,
and the and operator (∧), defined by
0∧0 = 0∧1 = 1∧0 = 0,
determine whether this set contains any duplicates.
(a) Suggest an algorithm and find an order-of-magnitude expression for its
time-complexity.
(b) Examine if the implementation of the algorithm on a Turing machine
affects your conclusions.
2. Repeat Exercise 1, this time determining if the set contains any triplicates. Is
the algorithm as efficient as possible?
3. Review how the choice of algorithm affects the efficiency of sorting. What is
the time complexity of the most efficient sorting algorithms?
14.2 Turing Machine Models and Complexity
In the study of computability it makes little difference what particular model of
Turing machine we use, but we have already seen that the efficiency of a
computation can be affected by the number of tapes of the machine and by
whether it is deterministic or nondeterministic. As Example 12.8 shows,
nondeterministic solutions are often much more efficient than deterministic
alternatives. The next example illustrates this even more clearly.
Example 14.2
We now introduce the satisfiability problem (SAT), which plays an important
role in complexity theory.
A logic or boolean constant or variable is one that can take on exactly two
values, true or false, which we will denote by 1 and 0, respectively. Boolean
operators are used to combine boolean constants and variables into boolean
expressions. The simplest boolean operators are or, denoted by V and defined by
0∨1 = 1∨0 = 1∨1 = 1,
0∨0 = 0,
and the and operator (∧), defined by
0∧0 = 0∧1 = 1∧0 = 0,