Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMPUTABILITY AND COMPUTATIONAL COMPLEXITY - Coggle Diagram
COMPUTABILITY AND COMPUTATIONAL COMPLEXITY
Class-NP
Non-deterministic: generating an arbitrary candidate solution
Deterministic: checking whether it is a solution indeed
the class of decision problems that can be
solved in polynomial time by non-deterministic algorithms
NP-Complete
the most difficult problems in NP
it belongs to the class NP
every problem in NP is polynomially reducible to D
A decision problem D1 is said to be polynomially reducible to a decision problem D2, if there exists a function t that transforms instances of D1 to instances of D2 such that:
For all instances i ∈ D1, the answer of i is yes
if, and only if, the answer of t(i) ∈ D2 is yes
t is computable by a polynomial time algorithm
Computability
There are problems: tractable and intractable, but they are decidable
There are undecidable problems (non-computable)
Halting problem
How to address intractible and (even worse!) undecidable problems?
Backtracking
Branch and bound
Dynamic programming
Approximation algorithms
Heuristics
Entscheidungsproblem