Please enable JavaScript.
Coggle requires JavaScript to display documents.
M15 - Algorithms and Data Structures , if (ODD(n)), n = 3 * n + 1;, else,…
M15 - Algorithms and Data Structures
17 Limits to Computation
17.1 Reductions
Reduction allows us to solve one problem in terms of another.
when we wish to understand the difficulty of a problem, reduction allows us to make relative statements about upper and lower bounds on the cost of a problem
When you buy or write a program to solve one problem, such as sorting, you might be able to use it to help solve a different problem. This is known in software engineering as
software reuse
Notice that reduction is a three-step process.
The first step is to convert an instance of PAIRING into two instances of SORTING.
The second step is to sort the two arrays
The third step is to convert the output of SORTING to the output for PAIRING
A reduction of PAIRING to SORTING helps to establish an upper bound on the cost of PAIRING
We can define reduction more formally as a three-step process:
Transform an arbitrary instance of the first problem to an instance of the second problem. In other words, there must be a transformation from any instance I of the first problem to an instance I' of the second problem.
Apply an algorithm for the second problem to the instance I', yielding a solution SLN'
Transform SLN' to the solution of I, known as SLN. Note that SLN must in fact be the correct solution for I for the reduction to be acceptable.
17.2 Hard Problems
17.2.1 The Theory of NP- Completeness
The idea of “guessing” the right answer to a problem is called
non-determinism
an algorithm that runs on a non-deterministic machine in polynomial time is given a special name: It is said to be a problem in
NP
.
problems that can be solved in polynomial time on a non-deterministic machine
A
decision problem
is simply one whose answer is either YES or NO
We know efficient non-deterministic algorithms, but we do not know if there are effcient deterministic algorithms. At the same time, we have not been able to prove that any of these problems do not have efficient deterministic algorithms
This class of problems is called
NP-complete.
A problem X is defined to be NP-complete if:
1. X is in NP; 2. X is NP-hard.
How is NP-completeness of practical significance for typical programmers?
if you can prove that the problem is NP-complete, you are in effect saying that the most brilliant computer scientists for the last 50 years have been trying and failing to find a polynomial time algorithm for her problem
Problems that are solvable in polynomial time on a regular computer are said to be in
class P.
if we were able to prove that TRAVELING SALESMAN has an exponential time lower bound, then we would know that P 6= N P
17.2.2 NP-Completeness Proofs
prove problems are NP-complete
The first proof that a problem is NP-hard (and because it is in NP, therefore NP-complete) was done by Stephen Cook.
The “grand-daddy” N P-complete problem that Cook used is call SATISFIABILITY (or
SAT
for short).
Input: A Boolean expression E over variables x1, x2, ... in Conjunctive Normal Form
Output: YES if there is an assignment to the variables that makes E true,
NO otherwise
17.2.3 Coping with NP-Complete Problems
Finding that your problem is NP-complete might not mean that you can just forget about it
Traveling salesmen need to find reasonable sales routes regardless of the complexity of the problem
What do you do when faced with an NP-complete problem that you must solve?
Consider the Knapsack problem, we have a dynamic programming algorithm whose cost is Θ(nK). But it turns out that Knapsack is NP-complete.
This dynamic programming algorithm is tractable if the numbers are “reasonable.
Such an algorithm is called a
pseudo-polynomial
time algorithm.
we define a hard algorithm to be one that runs in exponential time, that is, in Ω(c^n) for some constant c > 1
17.3 Impossible Problems
17.3.1 Uncountability
the Halting Problem
while (n > 1)
17.3.2 The Halting Problem Is Unsolvable
if (ODD(n))
n = 3 * n + 1;
else
n = n / 2;