431
to find the largest element of an unsorted list of numbers, an algorithm must look
at all the numbers in the list and keep a record of the largest number it has seen
so far. The algorithm must look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it is handling.
Although many problems are class P, there are harder problems.
Class NP problems: NP stands for “nondeterministic polynomial time.”
These kinds of problems are the ones that cannot be solved in polynomial time
unless there are some “hints” given. In other words, these problems have polynomial time verifiers. Deciding is hard for such problems, but verifying a given
example is easier. For example, finding prime factors of a large number is an NP
problem. Verifying a solution requires some multiplications but solving the
problem is much harder since it requires systematically trying out all the
candidates.
NP-hardness: These are the problems, which most people believe cannot be
solved in polynomial time, even though nobody can prove a super-polynomial
lower bound. Intuitively, this is like saying that if we could solve one particular
NP-hard problem quickly, then we could quickly solve any problem whose
solution is easy to understand, using the solution to that one special problem as
a subroutine (Karpinski & Kannan 2004). NP-hard problems are at least as hard
as any problem in NP. For example, the number of colors needed to color a map
such that the neighboring regions do not have the same color is considered to be
an NP-Hard problem to solve.
NP-completeness: NP-Complete problems are the hardest problems to solve
among the NP problems. For those, no polynomial time algorithm has yet been
discovered, nor has anybody yet been able to prove that no polynomial-time
algorithm exists for any of them. The interesting part is, if any one of the NP
complete problems can be solved in polynomial time, then all of them can be
solved. An example of an NP-Complete problem is energy generation and
scheduling. Suppose there are hundreds of energy generators. Scheduling the
turn on and shut down operations of these generators by the changing variables
(demand, etc.) is proved to be NP-Complete.
(b) Space (Memory) complexity: Just like the fact that the computational (time)
complexity measures the amount of computing resources an algorithm uses;
memory complexity defines the memory space that an algorithm uses. For the
space complexity, several aspects need to be considered. These are the amount
of memory for the code of the algorithm, the input data, the output data and the
space for the intermediate steps of the algorithm (workspace for the algorithm
execution). Although these were equally important in history, today the most
important one is the amount of memory needed for the intermediate steps of the
algorithm.
From a practical perspective, algorithms and data structures are not the only
concerns for efficient program design. An efficient algorithm may perform differently on different platforms due to the use of different development platforms. To
understand the performance variability between platforms, one may need to under16 Computing
to find the largest element of an unsorted list of numbers, an algorithm must look
at all the numbers in the list and keep a record of the largest number it has seen
so far. The algorithm must look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it is handling.
Although many problems are class P, there are harder problems.
Class NP problems: NP stands for “nondeterministic polynomial time.”
These kinds of problems are the ones that cannot be solved in polynomial time
unless there are some “hints” given. In other words, these problems have polynomial time verifiers. Deciding is hard for such problems, but verifying a given
example is easier. For example, finding prime factors of a large number is an NP
problem. Verifying a solution requires some multiplications but solving the
problem is much harder since it requires systematically trying out all the
candidates.
NP-hardness: These are the problems, which most people believe cannot be
solved in polynomial time, even though nobody can prove a super-polynomial
lower bound. Intuitively, this is like saying that if we could solve one particular
NP-hard problem quickly, then we could quickly solve any problem whose
solution is easy to understand, using the solution to that one special problem as
a subroutine (Karpinski & Kannan 2004). NP-hard problems are at least as hard
as any problem in NP. For example, the number of colors needed to color a map
such that the neighboring regions do not have the same color is considered to be
an NP-Hard problem to solve.
NP-completeness: NP-Complete problems are the hardest problems to solve
among the NP problems. For those, no polynomial time algorithm has yet been
discovered, nor has anybody yet been able to prove that no polynomial-time
algorithm exists for any of them. The interesting part is, if any one of the NP
complete problems can be solved in polynomial time, then all of them can be
solved. An example of an NP-Complete problem is energy generation and
scheduling. Suppose there are hundreds of energy generators. Scheduling the
turn on and shut down operations of these generators by the changing variables
(demand, etc.) is proved to be NP-Complete.
(b) Space (Memory) complexity: Just like the fact that the computational (time)
complexity measures the amount of computing resources an algorithm uses;
memory complexity defines the memory space that an algorithm uses. For the
space complexity, several aspects need to be considered. These are the amount
of memory for the code of the algorithm, the input data, the output data and the
space for the intermediate steps of the algorithm (workspace for the algorithm
execution). Although these were equally important in history, today the most
important one is the amount of memory needed for the intermediate steps of the
algorithm.
From a practical perspective, algorithms and data structures are not the only
concerns for efficient program design. An efficient algorithm may perform differently on different platforms due to the use of different development platforms. To
understand the performance variability between platforms, one may need to under16 Computing