Platzhalter
problems in P
for n size of the input, there is an algorithm that solves the problem in running time O(n^c), so in polynomial time
problems in NP
problems that can be verified in polynomial time
Boolean satisfiability problem (SAT)
Asks whether there exists an interpretation that satisfies a given Boolean formula. SAT is in NP, because it can be verified quickly. It’s also NP hard (some theorem), thus it is NP-complete.
It can be answered in O(2^n)
Reduction: If we reduce a problem B to another problem A …
… A is at least as difficult as B
Linked List
adjacency matrix
List of edges
Upper bound for |E|
depth first search algorithm
breadth first search algorithm
O notation
halting problem
decision problem
example
optimisation problem
language
when does a Turing Machine decide a language?
The class P (using languages)
The class NP (using languages)
Instance
CNF
3-SAT
Reduction 3-SAT -> independent set
block (2 definitions)
Menger’s Theorem
Reduction 3-SAT -> 3-colouring
block graph
FPT: A parameterized problem is called fixed parameter tractable if …
definition tree-decomposition
Lemma: transfer of separation properties from tree-decomposition to G
proof
width
tree-width
small tree-decomposition
property that follows
How to generate a tree-decomposition of small tree-width
Last changed8 days ago
