Computability and Computational Complexity - Coggle Diagram
Computability and Computational Complexity
problems that can be solved in
(algorithms in O(p(n)), where p(n) is a polynomial in terms of n).
problems that cannot be solved in
the class of decision problems that can be solved in polynomial time by deterministic algorithms
Decision problems with
Many important problems are not decision problems, but
they can be reduced to a series of decision problems
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
Graph coloring problem
can be difficult, checking
solution can be easy
the class of decision problems that can be
by non-deterministic algorithms
P ⊆ NP
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.
A non-deterministic algorithm solves a decision problem if it is capable
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.
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 = ∅
There are problems: tractable and intractable, but they are decidable.
There are undecidable problems (non-computable)
How to address intractible and (even worse!) undecidable problems?
Branch and bound