Algorithms and Complexity: NP

Flashcards on Algorithms and Complexity: NP

What is the aim of today’s lecture?

To formally define problems in NP and consider how to determine if a problem is in NP.

What are P problems?

Problems solvable in polynomial time.

What are NP problems?

Decision problems with solutions that can be “checked” in polynomial time.

What is the relationship between P and NP?

P is a subset of NP, but we don’t know if it’s a proper subset as we don’t know if P=NP (most people think P≠NP)

What is a decision problem?

In a decision problem the answer is either “yes” or “no”.

What is a decidable problem?

A decision problem that can be solved by an algorithm.

What are optimization problems?

Requires that some value be minimized (e.g., finding shortest paths) or maximized (e.g., finding longest paths).

How can we easily convert an optimization problem to a decision problem?

By asking: is there a solution that has value lower than (or higher than) a given value?

What is an abstract problem?

A binary relation mapping problem instances to problem solutions.

What are Decision problems?

Those having a “yes”/ “no” answer.

Give an example of a decision problem

A decision problem : given a directed graph vertices and , and an integer , = (,), does a path exist from to consisting of at most edges?

What is the TSP Optimization problem?

Given a list of cities and the pairwise distances between cities. What is the shortest possible route that visits each city exactly once and returns to the origin city?

What is the TSP Decision problem?

Given a list of cities and the pairwise distances between cities. Is there a route through every city (and back to the start) with distance travelled less than a given constant without revisiting the same cities?

What is Clique Optimization Problem?

Given a graph what is the largest clique?

What is Clique Decision problem?

Given a graph does there exist a clique of at least size (where is a given constant)?

What are P (Polynomial time) problems?

Decision problems for which there is a polynomial time algorithm.

What are NP (Non-deterministic polynomial time) problems?

Decision problems that can be “checked” in polynomial time.

What is Non-determinism?

“try everything” and if any of them work, they return “yes”.

How do Non-deterministic algorithms work?

May return different results each time they are called with a specific set of input values, but guaranteed to lead to “accept” outcome if possible.

What is a Certifier?

Polynomial-time algorithm that takes two inputs: A string, which is an instance of A string, which acts as a “certificate” or “witness” that ∈
And returns false (regardless of ) if ∉
True for at least one string if ∈

What is NP?

Set of decision problems with a polynomial time certifier