Rather, it is because the day-to-day problems are one for which there is no
known practical solution.
7.3 NON-DETERMINISTIC POLYNOMIAL TIME ALGORITHMS
A nondeterministic computation is viewed as:
(i) when a choice point is reached, an infallible oracle can be
consulted to determine the right option.
(ii) When a choice point is reached, all choices are made and
computation can proceed simultaneously.
A Non-deterministic Polynomial Time Algorithm is one that can be
executed in polynomial time on a nondeterministic machine. The machine can
either consult an oracle in constant time, or it can spawn an arbitrarily large
number of parallel processes, which is obviously a nice machine to have.
Summary to common time complexities:
Com plex ity
Ver bal Descrip tion
Feasilality
O(1)
con stant time
fea si ble
O
n
(log )
log time
fea si ble
O n
( )
lin ear time
fea si ble
O n
n
( log )
log lin ear time
fea si ble
O n
( )
2
qua dratic time
some times fea si ble
O n
( )
3
cubic time
less often fea si ble
O
n
( )
2
expo nen tial time
rarely fea si ble
7.4 INTEGER BIN PACKING
Assume we are given a set of n integers. Our task is to arrange these integers
into two piles or bins, so that the sum of the integers in one pile is equal to the
sum of the integers in the other pile.
For example, given the integers
{19, 23, 32, 42, 50, 62, 77, 88, 89, 105, 114, 123, 176}
These numbers sum to 1000. Can they be divided into two bins, bin A and
bin B, such that the sum of the integers in each bin is 500?
There is an obvious nondeterministic algorithm: For each number, put it in
the correct bin. This requires linear time.
There is also a fairly easy deterministic algorithm. There are 13 numbers
(n = 13), so form the 13-bit binary number 0000000000000.
Complexity Theory
237