Introduction¶

Algorithmic Problems¶

Decision problems: yes/no
- Given a graph G, is G connected?
- Given a graph G, is G 3-colorable?
- Given a boolean formula phi, is phi satisfiable?
- Given a natural number M, is M a prime?
Function problems
- Given 2 integers M and N, find the GCD
- Given a network of cities and distances, find the length of minimal length
Enumeration problems
- Given a natural number, find its prime factors
- Given a boolean formula phi, find all/how many satisfying assortments
Optimization problems
- Given a network of cities and distances, find a tour of minimal length

In general, decision problems are the easiest to solve - and any problem can be expressed as a series of decision problems