Please enable JavaScript.
Coggle requires JavaScript to display documents.
Computability and Computational Complexity - Coggle Diagram
Computability and Computational Complexity
Tractable Problem
problems that can be solved in
polynomial time
(algorithms in O(p(n)), where p(n) is a polynomial in terms of n).
Intractable Problem
problems that cannot be solved in
polynomial time
.
Complexity Classes
P
the class of decision problems that can be solved in polynomial time by deterministic algorithms
Decision problems with
yes/no
(true/false) answers
Many important problems are not decision problems, but
they can be reduced to a series of decision problems
For example,
instead of asking about the minimum number of colors needed to color the vertices of a graph so that no two adjacent vertices are colored the same color
, we can ask whether there exists such a coloring of the graph’s vertices with no more than m colors for m = 1, 2,.... (The latter is called the m-coloring problem.) The first value of m in this series for which the decision problem of m-coloring has a solution solves the optimization version of the graph-coloring problem as well.
There are many important problems for which
no polynomial-time algorithm has been found so far
TSP – travelling salesman problem
Subset sum problem
Knapsack problem
Graph coloring problem
Although
solving
can be difficult, checking
a candidate
solution can be easy
(tractable)
NP
the class of decision problems that can be
solved in
polynomial time
by non-deterministic algorithms
P ⊆ NP
Non-deterministic algorithms
Non-deterministic: generating an arbitrary candidate solution
Deterministic: checking whether it is a solution indeed.
A non-deterministic algorithm is said to be non-deterministic
polynomial if the time efficiency of its verification stage is polynomial.
two-stage procedure:
A non-deterministic algorithm solves a decision problem if it is capable
of
guessing a solution
at least once and to be able to verify its validity.
Yes: if there is at least one way of performing non-deterministic
jumps in order to find a valid solution.
No: otherwise
NP-Complete
Informally, NP-complete: the most difficult problems in NP
If P != NP, then
P ⊂ NP
P ∩ NP-complete = ∅
NP-intermediate = NP − NP-complete − P
If P = NP, then
P = NP = NP-Complete
NP-intermediate = ∅
Computability
There are problems: tractable and intractable, but they are decidable.
There are undecidable problems (non-computable)
Halting problem
Entscheidungsproblem
How to address intractible and (even worse!) undecidable problems?
Backtracking
Branch and bound
Dynamic programming
Approximation algorithms
Heuristics