Computational Complexity

Question 1

Computational complexity of a problem

Answer 1

Refers to the most optimal algorithm known for solving the specific problem.

Question 2

Complexity Class P

Answer 2

• Polynomial: problems that are solvable in polynomial time.
• • *

Question 3

Optimization problems and decision problems

Answer 3

Computational complexity uses decisional problems for which only a yes or no answer exists.

For each optimization problem, there exist a decisional version.

The standard way to define the decisional version of an optimization problem conists in 2 parts:

• defining the instance assigning values to the parameters of the problem
• set a question relative to the instance, that can be answered with yes or no.

Question 4

Yes-instance

Answer 4

Is an instance of a problem that yields the answer “yes” to the problem.

Question 5

NP algorithm

Answer 5

Given a decision problem, a non-deterministic algorithm for such problem is divided in 2 phases:

• 1: (hypothesis) The existence of a particular yes instance is assumed given a decision problem and a yes-certificate is available to check the hypothesis
• 2 (verification): The correctness of the hypothesis is verified.
  
  • if this phase has polynomial complexity, then the algorithm is said to be non-deterministic polynomial.

Question 6

Reducibility

Answer 6

A problem w’ is polynomially reducible to another problem w (represented with w’ ∝ w) if for any instance w’ it is possible to construct in polynomial time an instance of w such that from the optimal solution of the considered instance of w, we can determine in polynomial complexity the optima solution for the instance w’.

In terms of complexity, w’ ∝ w means that w is at least as difficult as w’.

Reducibility operator satisfies the transitivity relation:

w ∝ w’ and w’ ∝ w’’, then w ∝ w’’.

Question 7

Cook’s theorem

Answer 7

If a problem w ∈ NP, then w ∝ SAT.

Or: any problem that is part of NP is reducible to the Satisfiability problem.

This allows to introduce the NP-complete class of problems.

Question 8

Complexity Class NP

Answer 8

Non-deterministic Polynomial (NP): the set of all decision problems that can be solved in the worst case by a non-deterministic polynomial algorithm.

Question 9

Complexity Class NP-complete

Answer 9

NP-complete problems are important, because if a polynomial algorithm is found that solves one NP-complete problem, then any NP problem could be solved in polynomial time, that would amke NP = P.

This means that any problem in NP is at least as difficult to solve as SAT.

NP-Complete: any problem w such that :

• 1: w ∈ NP
• 2: SAT ∝ w

Every NP-complete problem has the same difficulty: consider the pair of NP-complete problems w and w’:

• w ∝ SAT
• SAT ∝ w’

Theorem: A problem w is NP-complete if

• w ∈ NP
• ∃ w’ NP-complete such that w ∝ w’

Question 10

NP-hard complexity class

Answer 10

Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.

The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

Question 11

Complexity class: pseudo-polynomial

Answer 11

Pseudo-polynomial: if for each input instance I, the corresponding upper bound execution time is limited by a polynomial in |I| and max(I).

Question 12

P = NP