Download - 2. Complejidad 2012-I
-
8/2/2019 2. Complejidad 2012-I
1/62
Inefficienc and Intractabilit
-
8/2/2019 2. Complejidad 2012-I
2/62
Introduction
There are problems for which: are solved by different algorithms.
forever (and ever)!
there are no known algorithms that solve them.
-
8/2/2019 2. Complejidad 2012-I
3/62
Towers of Hanoi (I)
What is the time complexity of the best algorithm
that solves it?
-
8/2/2019 2. Complejidad 2012-I
4/62
Towers of Hanoi (II)
The time complexity of the best knownalgorithm is 2N -1.
moves is also 2N -1.
The solution is optimal!
-
8/2/2019 2. Complejidad 2012-I
5/62
Towers of Hanoi (III)
The original problem had 64 rings. If onering could be moved every 10 seconds, it
would take over 5 trillion ears to solve the
problem.
Even moving 1 million rings a second takes
over 1/2 million years
-
8/2/2019 2. Complejidad 2012-I
6/62
Decision Problems
Perhaps part of the long running time of analgorithm is that we are looking for a
solution.
What if we just asked, Does a solution
exist?
A decisionproblem is one which has a yesorno answer.
-
8/2/2019 2. Complejidad 2012-I
7/62
Most problems have a decision problemversion.
For example: What is the minimum grade I
can get on the final and still get an A in the
class?
The decision problem version is: If I get a(some number) on the final, will I still get
an A in the class?
-
8/2/2019 2. Complejidad 2012-I
8/62
The Monkey Puzzle (I)
-
8/2/2019 2. Complejidad 2012-I
9/62
The Monkey Puzzle (II)
Would you please give a naive algorithm tosolve this problem?
-
8/2/2019 2. Complejidad 2012-I
10/62
The Monkey Puzzle (III)
Given N cards, a brute-force solution takesN! steps.
takes over 490 billion years for 25 cards.
For N=36, it would take far far longer than
the time elapsed since the Big Bang!
-
8/2/2019 2. Complejidad 2012-I
11/62
The Monkey Puzzle (IV)
Arrangements that are easier to solve: All N cards are either of:
-
8/2/2019 2. Complejidad 2012-I
12/62
The Monkey Puzzle (V)
The worst case is what matters. The performance of the most efficient
naive one.
Can there be an algorithm that takes
reasonable time?
-
8/2/2019 2. Complejidad 2012-I
13/62
NKvs N! N! vs NN
Different Functions of TimeComplexity (I)
2N vs NK
What is the order?
-
8/2/2019 2. Complejidad 2012-I
14/62
Different Functions of TimeComplexity (II)
Algorithms whose run time is bounded fromabove by a polynomial function of N are
called ol nomial-time al orithms.
The other algorithms are calledpolynomial-
time algorithms. Well call them
exponential algorithms.
-
8/2/2019 2. Complejidad 2012-I
15/62
Different Functions of TimeComplexity (III)
-
8/2/2019 2. Complejidad 2012-I
16/62
-
8/2/2019 2. Complejidad 2012-I
17/62
Different Functions of TimeComplexity (V)
-
8/2/2019 2. Complejidad 2012-I
18/62
Reasonable Algorithms
Examining the previous three slides we findthat some algorithms might be reasonable
and others not reasonable.
Polynomial-time algorithms are said to bereasonable.
-
8/2/2019 2. Complejidad 2012-I
19/62
Unreasonable Algorithms
An algorithm which has an exponential orsuper-exponential upper bound is said to be
unreasonable.
Note that an intractable algorithm has a
solution. It just takes an unreasonably long
time to find it.
-
8/2/2019 2. Complejidad 2012-I
20/62
Reasonable Vs UnreasonableAlgorithms (I)
Consider N1000 and N!.. Which one is better
for values lower than1500?
-
8/2/2019 2. Complejidad 2012-I
21/62
Reasonable Vs UnreasonableAlgorithms (II)
However, the vast majority of reasonablealgorithms that take NKhave a K no greater
that 5 or 6.
Thus, most of the reasonable algorithms are
useful and most of the unreasonable
algorithms are useless.
-
8/2/2019 2. Complejidad 2012-I
22/62
Tractable and IntractableProblems
-
8/2/2019 2. Complejidad 2012-I
23/62
More on the Monkey Puzzle
1. Computers are becoming faster by theweek. Over the last 10 years or so
com uter s eed has increased rou hl b a
factor of 50. Perhaps obtaining a practicalsolution to the problem is just a question of
awaiting an additional improvement in
computer speed.
-
8/2/2019 2. Complejidad 2012-I
24/62
2. Doesnt the fact that we have not found abetter algorithm for this problem indicate
our incompetence at devising efficient
algorithms? Shouldnt computer scientistsbe working at trying to improve the
situation rather than s endin their time
teaching classes about it?
3. Havent people tried to look for an
exponential-time lower bound on the
problem, so that we might have aproof that
no reasonable algorithm exists?
-
8/2/2019 2. Complejidad 2012-I
25/62
4. Maybe the whole issue is not worth theeffort, as the monkey puzzle problem is
just one specific problem. It might be a
colorful one, but it certainly doesnt looklike a very important one.
-
8/2/2019 2. Complejidad 2012-I
26/62
Reply to point 4: It so happens that theMonkey Puzzle problem is not alone.
There are close to 1000 diverse algorithmic
problems like this one.
They have the amazing property that if we
,
-
8/2/2019 2. Complejidad 2012-I
27/62
Problems NP-Complete (I)
Problems which have intractable solutions.But, none are known not to have tractable
solutions.
No one has proven they require super-polynomial time!!!
The best-known lower bounds are
(N).
-
8/2/2019 2. Complejidad 2012-I
28/62
Problems NP-Complete (II)
They are complete. That means that if wesolve one of them, we can solve all of them.
,
exponential lower bound, that applies for allof them!
-
8/2/2019 2. Complejidad 2012-I
29/62
Some NPC Problems
Generalized jigsaw or arrangement Graph problems
Hamiltonian path
Scheduling and Matching problem
Determining Logical Truth Map Colorings
Graph Coloring
-
8/2/2019 2. Complejidad 2012-I
30/62
Airline puzzle
Can they form a rectangle?
-
8/2/2019 2. Complejidad 2012-I
31/62
Ordinary Puzzle
If just one piece can fit in a given place, thetime complexity is cuadratic.
NPC because partial matches may not leadto a complete solution.
-
8/2/2019 2. Complejidad 2012-I
32/62
Traveling-Salesman Problem
What is the naive solution? What is its
complexity?
-
8/2/2019 2. Complejidad 2012-I
33/62
Hamiltonian Path
What is its complexity?
-
8/2/2019 2. Complejidad 2012-I
34/62
Other problems
Determining Logical Truth Map Colorings
Gra h Colorin
-
8/2/2019 2. Complejidad 2012-I
35/62
Nondeterminism
The notion of nondeterminism is rather non-intuitive.
algorithm as an abstract notion, not as arealistic goal.
-
8/2/2019 2. Complejidad 2012-I
36/62
Nondeterminism is important to thedevelopment of the theory and the
explanation of the existence of this class of
problems. A nondeterministic algorithm has, in
deterministic algorithm, a very powerfuloracle.
-
8/2/2019 2. Complejidad 2012-I
37/62
Problems solved by nondeterministic
algorithms have the property that they cantake an unacceptably long time to produce a
solution. If a solution is arrived at,
however, there is an easy way to convince
someone that it is a solution.
-
8/2/2019 2. Complejidad 2012-I
38/62
Polynomial-Time Reduction (I)
Given two NP-Complete problems, apolynomial-time reduction is an algorithm
that runs in ol nomial time and reduces
one problem to the other. If problem X can be polynomically reduced
to problem Y. It means that X is no worse
than Y.
-
8/2/2019 2. Complejidad 2012-I
39/62
Polynomial-Time Reduction (II)
Example
-
8/2/2019 2. Complejidad 2012-I
40/62
Polynomial-Time Reduction (III)
-
8/2/2019 2. Complejidad 2012-I
41/62
Exercise
How would you polynomically reduce the3-coloring problem to the satisfiability
roblem?
N countries C1, C2, , CN
Colors R (red), B (blue), Y (yellow)
Propositional sentence F
-
8/2/2019 2. Complejidad 2012-I
42/62
Solution
3N assertions why?
What is the time of the reduction?
-
8/2/2019 2. Complejidad 2012-I
43/62
Showing that a problem is NP-Complete (I)
Cooks remarkable theorem proved thatthere exists NP-completeproblems. In
articular he demonstrated the SAT was
NP-complete (1971). Cooks theorem makes showing a problem
is NP-complete easier.
-
8/2/2019 2. Complejidad 2012-I
44/62
Showing that a problem is NP-Complete (II)
New problem R You must prove that you can
Reduce R to a NP-Complete problem Q (or
show a certificate/non-deterministic magical
algorithm).
Reduce a NP-Complete problem S to R (or use
a theorem)
-
8/2/2019 2. Complejidad 2012-I
45/62
Where are the NP-Completeproblems in the sphere?
-
8/2/2019 2. Complejidad 2012-I
46/62
Class P
The class P is comprised by the set ofproblems that are tractable, i.e. problems
that can be solved b a deterministic-
polynomial time algorithm.
-
8/2/2019 2. Complejidad 2012-I
47/62
Where are the P problems in thesphere?
-
8/2/2019 2. Complejidad 2012-I
48/62
Class NP (I)
NP is the set of all decision problems for which
the instances where the answer is "yes" haveefficiently verifiable proofs of the fact that the
answer s n ee yes.
More precisely, these proofs have to be
verifiable in polynomial time.
The hardest problems in NP are NP-Complete
problems.
-
8/2/2019 2. Complejidad 2012-I
49/62
Class NP (II)
P = NP ? First asked in 1971
Is there NP-Intermediate?
-
8/2/2019 2. Complejidad 2012-I
50/62
P = NP? (I)
Its clear that is P
NP, but P====
NP ? No one has yet demonstrated a problem that
To prove P = NP requires us to show that
every problem in NP can be solved by a
deterministic polynomial time algorithms.
Nobody has done this either!
-
8/2/2019 2. Complejidad 2012-I
51/62
NP-Intermediate Problems (I)
Set of problems that are in the complexityclass NPbut are neither in the class P nor
NP-com lete.
The class of such problems is called NPI.
-
8/2/2019 2. Complejidad 2012-I
52/62
NP-Intermediate Problems (II)
Ladner's theorem, shown in 1975, is a
result asserting that:
IfP NP, then NPI is not empty; that is, NP
con a ns pro ems a are ne er n nor -
complete.
P = NP if and only if NPI is empty.
NPI Candidates: graph isomorphism problem
computing the discrete logarithm.
-
8/2/2019 2. Complejidad 2012-I
53/62
NP-Hard Problems (I)
At least as hard as the hardest problems inNP.
-
is an NP-complete problem L that ispolynomically reducible to X.
This means that no problem in NP is harder
than X.
-
8/2/2019 2. Complejidad 2012-I
54/62
NP-Hard Problems (II)
-
8/2/2019 2. Complejidad 2012-I
55/62
NP-Hard Problems (III) A problem X is called an NP-complete
problem if (1) it belongs to NP and (2) it is NP-hard.
o e a , a -comp e epro em can e
solved by a deterministic polynomial
algorithm, then P = NP.
Also, if any NP-hardproblem is shown to bein P, then P = NP.
-
8/2/2019 2. Complejidad 2012-I
56/62
Optimizations Problems that areNP-Complete
NP-completeproblems are usually taken as thedecisionproblem (yes/no) version of
o timization roblems. E. . TSP.
Finding an optimal tour cannot be tractable
without the yes/no version being tractable too.
The original problem is also said to be NP-Complete.
-
8/2/2019 2. Complejidad 2012-I
57/62
Imperfect Solutions to NP-Complete Problems (I)
But, humans manage to solve theseproblems all the time in short time!
Approximation algorithms find solutionsless than perfect, yet of practical value.
Some of them are guaranteed to be close the
optimal solution.
-
8/2/2019 2. Complejidad 2012-I
58/62
Imperfect Solutions to NP-Complete Problems (II)
Some of them are guaranteed to be close theoptimal solution.
Ex: Cubic algorithm that always produces a
result at most 1.5 worse than the optimal.
Some of them produce a solution very close
to the optimal solution almost always. Ex: Algorithm that parts the graph and
combines local solutions.
-
8/2/2019 2. Complejidad 2012-I
59/62
Provably Intractable Problems
We are not able toprove that problems inNP have no tractable solution
ere are pro ems, owever, suc as t e
Towers Of Hanoi, that can be shown to
have an exponential lower bound and that
have no certificate.
-
8/2/2019 2. Complejidad 2012-I
60/62
Class Co-NP
Class of problems for which efficientlyverifiable proofs ofno instances, sometimes
called counterexam les .
Example ofNP-Complete: Given a finite set ofintegers is there a non-empty subset which
sums to zero?
Example ofco-NP: Given a finite set ofintegers, does every non-empty subset have a
nonzero sum?
Complexity Classes
-
8/2/2019 2. Complejidad 2012-I
61/62
Complexity Classes
Theoretical Computer Scientists talk about a
hierarchy of complexity classes.
These classes are for both time and space
requirements.
-
8/2/2019 2. Complejidad 2012-I
62/62
Research on Complexity Classes
Some theorists work with questions such as:Is P = NP? orIs NP = co-NP? orCan we
re ine the com lexit classes?
Others work to develop approximate
solutions or heuristic solutions or alternate
models of computation: genetic algorithms,neural networks, etc..