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

Problem Difficulties
--------------------

- Unsolvable
- Solvable
    - Untractable (NP runtime)
    - Tractable (polynomial runtime)