Complexity Issues

• Class P problems
• Class NP problems
• NP-complete problems
• Non-NP problems
• Decidable, semi-decidable and undecidable problems

1. Class P problems

Almost all algorithms considered so far run in worst-case polynomial time. The class of algorithms that run in polynomial time is called class P problems

These problems are called also "tractable" problems.

2. Class NP problems

For some problems there is no known polynomial-time algorithm.

Example: Given a boolean expression of n variables, find a set of variable assignments that satisfy the expression.

There is no known algorithm that will solve this problem in polynomial time. However, if we have a set of variable assignments, we can check in polynomial
time whether the expression is satisfiable or not.

A problem which can be solved by a series of guessing (non-deterministic) steps and whose solution can be verified as correct in polynomial time is said to be in class NP.

What is the meaning of NP

NP means non-deterministically polynomial. If we have a candidate for a solution, we can verify it in polynomial time. The difficult part is to generate all possible candidates. There is no known algorithm that will do this in polynomial time. A failed candidate does not provide useful information as to what to try next, so we have to investigate all possible alternatives, e.g. to try all permutations of possible variable assignments.

The term non-deterministic comes from the name of the automata used to describe such algorithms. An automaton can be viewed as a graph
with an initial state and one or more final states. The task is to find a path from the initial state to a final state.
The automaton can move from one state to another following some rules. At each state there are many applicable rules, and the automaton has to guess the right rules in order to find the solution - i.e. to find a path from the initial state to a final state.

NP algorithms are called "intractable".

Obviously, PÍ NP, but PÌ NP (or P = NP) is an open question

3. NP- complete problems

An NP-Complete problem is an NP problem with the property that any problem in NP can be reduced to it in polynomial time.

In 1971 Stephen Cook (currently working at the University of Toronto, Ontario) showed that the satisfiability problem is NP-complete by proving that
every other NP problem could be transformed to it.

If we can solve one NP-complete problem in polynomial time, we can solve every problem in NP in polynomial time. For this reason, many assume P¹ NP.

Other NP-complete problems:

Bin packing problem: How to pack or store objects of various sizes and shapes with a minimum of wasted space?

Clique problem: A clique is a subset K of vertices in an undirected graph G such that
every pair is joined by an edge in G. The problems are:

1. Given a graph G, and an integer k, does G have a clique consisting of k vertices?
2. Given a graph G, find a clique with as many vertices as possible.

Knapsack problem: You have a knapsack with a given size and several objects with various sizes and values. The problem is how to fill your knapsack with these objects so that you have a maximum total value.

Hamiltonian Cycle: a cycle that contains all nodes of the graph. Proving that a graph has a Hamiltonian cycle is a NP-complete problem.

4. Non-NP problems

NP problems and non-NP problems:

For NP problems, given a candidate for a solution, we can verify it in polynomial time.

For non-NP problems, we cannot verify in polynomial time whether a candidate for a solution is a solution or not. For example, the problem to prove that a graph does not have a Hamiltonian cycle is a non-NP problem.
5. Decidable, semi-decidable and undecidable problems

Yes/No problems (decision problems)

A decision problem is a question that has two possible answers yes or no.
The question is about some input.

Examples:

Given a graph G and a set of vertices K. Is K a clique?

Given a graph G and a set of edges M, is M a spanning tree?

Given a set of axioms (boolean expressions) and an expression,
is the expression provable under the axioms?

A problem is decidable if there is an algorithm (P, NP, or non-NP) that says yes
if the answer is yes, and no otherwise.

A problem is semi - decidable if there is an algorithm that says yes
if the answer is yes, however it may loop infinitely if the answer is no.

A problem is undecidable if we can prove that there is no algorithm
that will deliver an answer.

Examples of semi-decidable problems:

Example 1:

Given a set of axioms, prove that an expression is true.

Problem 1: Let the axioms be:

A v B

A v C

~B

Prove A.

To prove A we add ~A to the axioms.
If A is true then ~A will be false and this will cause a contradiction - the conjunction of all axioms plus ~A will result in False

(A v B) L ~A = B

B L (A v C) = (B L A) v (B L C)

B L ~ B = False

Problem 2: Let the axioms be:

A v B

A v C

~B

Prove ~A.

We add A and obtain:

(A v C) L A = A

(A v B) L A = A

A L ~B = A L ~B

(A L ~B) L (A v B) = A L ~ B

…..

This process will never stop, because the expressions we obtain
will always be different from False

Example 2: Given an infinite set of strings, determine whether a given string
belongs to the set or not.

Example of undecidable problem.

The halting problem

Let LOOP is a program that checks other programs for infinite loops:

LOOP(P) stops and prints "yes" if P loops infinitely

LOOP(P) enters an infinite loop if P stops

What about LOOP(LOOP)?

Here is a concise description of the Halting problem.