Generic approaches for solving algorithmic problems ::

Are all problems simple?

So far we’ve seen many problems for which efficient algorithms exist. such as :

Shortest paths in graphs
Sorting
etc..

==Is there always an efficient algorithm available?==

==We don’t know yet, but we strongly suspect it not to be the case ==

Decision Problems :

A ==decision problem== takes a string as input - adjacency list of graph - and outputs either ‘yes’ or ‘no’. -> Is a graph bipartite; is an array sorted in increasing order; is 17 a prime number ?

Search problems :

A ==search problem== takes a given input and searches it for a specific trait and returns one or not.

Examples would be :

finding spanning tree
finding a path between two vertices whose length is at most 10
finding a connectino between two nodes

Optimization problems ::

A ==optimization problems== tries to find a specific set within a given dataset. Finding that specific set, consumes more time than just executing a simple search problems.

Examples would be :

find minimal spanning tree
shortest path between …

Converting Search and Optimization problems to Decision problems ::

In principle, one can transform optimization problems into decision problems - caveats could apply.

Example of conversion :: Instead of shortest path problem, we consider the following approach :: Does there exists a path between x and y whose length is smaller 10? If found > one smaller 9 … until smallest found.

The formal approach in complexity theory is based on decision problems. In the following I will be sloppy and won’t always distinguish between decision problems and optimization problems.

Complexity class P ::

==A decision problem has polynomial running time== if there is a polynomial function p such that for every input of length n, the algorithm terminates in time $O (p (n))$

We denote by P the set of all (decision) problems with polynomial running time.

The problems in P are the ones we consider computationally “easy” - even though “polynomial” can still be slow => $n^{1000}$ .

Every algorithm we worked with so far: shortest path, mst, binary trees, binary search.

Complexity class NP

While the class P consists of problems that we can solve “efficiently” the class NP requires a weaker condition: It consists of all decision problems for which we can verify yes-solutions in polynomial time.

Examples ::

Decision problem :: does there exist a path of length at most 10 between x and y
A yes-solution - witness - is as set of edges
The “certifier” has to verify that the witness forms a path and that is length is not longer than 10.

NP stands for “non-deterministic polynomial time” - an “oracle” presents a solution in some non-deterministic way : then we can verify this solution in polynomial time.

Example ::

reverting hash-values >> calculation
finding new prime number or validating whether a number is a prime number
TSP - traveling salesman :::

TSP :: given a graph with weighted edges.

We have to find the shortest tour that passes through all vertices and returns to the starting point, while also visiting each node at once max.

Maximal Cut - maxcut ::

Input : an undirected weighted graph (V,E) Output : a cut of the graph in two pieces, A, V\A such that the sum of weights of the edges between A and V\A is as large as possible

SAT - Satisfiability ::

Input : A boolean formular in “conjunctive normal form” :: KNF aus TI 1

Output : Either find an assignment of all the boolean variables x,y,… to the values true or false such that the whole statement becomes true, or report that no such assignment exists.

==funny enough== many problems dont seem to be that complex, and can seem rather easy until one thinks about it . Maxcut seems easy, because mincut is already easy.

==Every problem in P $\subset$ NP ::==

Reductions :: Comparing difficulty of problems ::

We want to say that some problems are at least as hard as other problems.

The tool we will use is :: reduction.

A ==polynomial-time reduction== is an algorithm A that takes the Instance $I_{4}$ of a decision problem $P_{4}$ as input and transforms it to an instance of $I_{5}$ of a different decision problem $P_{5}$ such that ::

$P_{1} (I_{1}) = yes ⟺ P_{2} (A (I_{2})) = yes$ $P_{1} (I_{1}) = n o ⟺ P_{2} (A (I_{2})) = n o$

Example :: ==Independent set –> clique==

“Independent set” : given an undirected graph and an integer k, decide whether there exists an independent set of size k, that is a set of k vertices who do not hav any edge in common.

“Clique” : given an undirected graph and an integer k, decide whether the graph ahs a subgraph of k vertices that is a clique.

We now want to construct a reduction from Independent set to clique.

Wir versuchen zwei verschiedene Probleme so zu kombinieren, dass man das eine auf das andere Problem reduzieren kann, sodass man die Laufzeitverhalten vergleichen kann.

Why are reductions interesting ? ::

==Intuition==: If we reduce P1 to P2, then P1 is “easier” than P@ - or at least not more difficult than it

More formally :: If we have a polynomial-time reduction from P1 to P2, and if P2 can be solved in polynomial time, then P1 can be solved in polynomial time as well.

Attention the statement does not hold the other way around!!

Wir können nicht annehmen, dass die Behauptung auch in Reverse funktioniert. Haben wir P1 reduziert P2, dann können wir nicht sagen : P2 schwierig ==> P1 schwierig. Es kann immernoch sein, dass P1 leicht ist

NP-Complete and NP-hard problems ::

A decision problem P is called NP-Hard if every problem in NP can be reduced in polynomial-time to problem P. $P 1 <= P$ –> wir können alle Probleme aus P auf NP abbilden und da gilt, dass P1 schwierig ist, dann muss auch P schwierig sein, gibt an, dass es das schwierigste Problem ist, was wir erreichen können, da alle P-Probleme weniger oder gleich schwer sind.

Intuitively such problems are very hard to solve hence the name.

==Further== A problem is called ==NP-complete== if two conditions are true :

The problem is in NP
the problem is in NP-Hard

Inituitively, NP-complete problems are “the most difficult problems in NP”

Gibt es ein Problem $P_{u lt r a}$ welches so grundlegend ist, dass man jedes andere Problem in NP auf dieses reduzieren kann ?

SAT ist NP-complete. ==Theorem of Cook(1971)== –> every problem in NP can be reduced in polynomial time to SAT!! One of the coolest results in theoretic computer science.

==General observations ::== Problems that are NP-complete in general might have efficient solutions if we restrict them to a smaller space of instances.

Examples ::

TSP is polynomial if we consider instances where all points live in a Euclidean space, for example cities in R^2 with euclidean distances –> heuristic approaches
Knapsack is polynomial if we restrict it to instances where all values and volumes are integers - dynamic programming

Unsolvable Problems ::

The one good thing abut many of the problems we have seen so far: they can be solved by a computer, it takes just a lot of time. But there are even problems whose solutions cannot be computed at all. In theoretical computer science you will get to know some of them we just discuss the issue informally.

“Informally”, a decision problem is called computable if there exists an algorithm that for any given instance, can compute in finite time whether the correct answer is yes or no.

==Example : halting algorithm==

Given any algorithm A - program - and an input I, the task of the halting problem is to decide whether the algorithm A is going to stop on instance I or whether it is going to run forever – infinitve loop.

We could wait until it finished operation - or not - but we cannot evaluate that it will ever terminate or not, because we cant observe it forever..

==Theorem:: There cannot exist any algorithm that solves the halting problem==

Proof Sketch == Widerspruchsbeweis

Assume we have a function terminates(A,I) that decides whether algorithm A is going to terminate with input I. Results with yes or no.
Now construct the following new functino that operates on binary strings :

function paradox(z)
	if(terminates(z,z))
		goto 2 >> we start endless loop

Paradox terminates == program z does not terminate when it is given its own code as input..

Ein Friseur, der alle rasiert und sich selbst rasiert.

Another problem :: polynomial equation ::

$x^{3} yz + 2 y^{4} z^{2} - 7 x z^{5} = 6$ are the integer values z,x,y that satisfy this equation ? Its not computable either …. Because :: theory of computation - ==Berechenbarkeitstheorie==

Classifications of Problems ::

The whole filed of complexity theory and theory of computtation ahs been exploring various classes of problems since the 1970ies. Some of the classes and relations they have found are shown on the next figures, just you get an impression.

Most famous problem in computer science ::

$P =^{?} NP$ ???? Most researchers believe that the answer is no.

If the answer was yes, then::

all of complexity theory collapses, we would be able to design a polynomial-time algorithm for NP-complete problems.
We could prove all mathematical theorems in polynomial time
cryptography would be impossible otherwise.

scattered-lenity