PINEAL.ME   Archives  About

NP problem

##Introduction

Plan

Explore the space of computationally hand problem to arrive at a mathematic characteristic a large d of them.

Technique

Compare negative difficultly of different problem.

P problem

Problems can find a polynomial time algorithm to solve.

NP problem

An algorithm that can be verified if it is a solution to a problem or not in polynomial time.

Loose definition

If problem X in at least as hard as problem Y. It means that if we could solve X, we could also solve Y.

Y X

Y is polynomial time reduced to X. If Y can be solved using a poly number of std computational steps plus a poly no of called to a black box to love X.

NP-Complete Problem

To prove a problem X is NPC problem:

  1. Prove it is a NP problem.
  2. Find a known NPC problem Y which satisfied $Y ≤_p X$.

NP hard Problem

To prove a problem X is hard problem:

  1. Find a known NPC problem Y which satisfied $Y ≤_p X$.

##Examples

###Independent Set Ref: Given a graph $G = (V,E)$, we say a set of nodes, $S \in V$ in independent if no two nodes in S and joined by an edge.

  1. Find the maximum size independent set in graph G.(Optimization version)

  2. Given a graph G and a number k, does G contain an independent set of size at least K.(Decision version)

  3. Ans: No solution.

###Vertex Cover Ref: Given a $graph G=(V,E)$ we say that a set of nodes $S \in V$ in a vertex cover if every edge $e \in E$ has at least one end in S.

  1. Find the smallest vertex cover set in G (Optimization version)

  2. Given a graph G=(V,E) and a number k, G contain a vertex cover of size at most k.(Decision version)

###Independent Set and Vertex Cover

FACT: let G=(V,E) be a graph then S in an independent set if and only if its complement (V-S) is a vertex cover.

S is an independent set.

**case 1 **

U is in S and V is not. V-S will have V and not U.

case 2 V is in S and U is not. V-S will have U and not V

case 3 Neither V or U are in the set

Suppose V-S is a vertex cover can prove that S is an independent set.

Claim: independent Set≤P vertex Cover Prove If we have a black box to solve the vertex cover problem. We can decide if G has independent set of size at least k by asking the black box if G has a vertex cover of size at most n-k.

Claim: Vertex cover ≤S independent Set

Proof: if we have a black box to solve the independent set we can deicide if G has a vertex cover of size at most k by asking the black box if G has an independent set of size at least n-k.

Set cover problem Given a set U of n elements, a collection s_1 to s_m of sub sets of U and and a number of k, does there exist a collection of at most k of these sets whose union is equal to all of U.

Set U = set of all edges in G S1 = {(1, 2), (1,3)} S2 = {(1,2), (2,3), (2,4), (2,5)}

Proof of correction: A) If we have a vertex cover of size k in G, then i can find a collection of k sets whose union is equal to all of U. B) If I have a collection of k sets, whose union is equal to all of U, then I can find a vertex cover of size k in G.

Given u bolean variable x1…xn a

a truth assignment fox X is an assignment of values 0 or 1 to each x_i

An assignment satisfies a change C if it causes C to evaluate 1.

An assignment satisfies a collection of if C1 and C2 and … CK evaluate to 1.

Given a set of closures C1 to Ck over a set of variables x - {x1, … xn} does there exist a satisfying truth

Problem statement Given a set of

Three set problem Given an

C1 = (x1, x2, x3)

Efficient Certification

ex: indenpendent set problem. certificate is a set of nodes of size at least k. certifier: go over every edge and check the if they are not both in S the edge is OK. check the size of set S.

Evaluate each clause

If X \in NP and for all Y \in NP

Is there a problem in NP that all other problem in NP can be reduced to it in polynomial time

Basic strategy to probe a problem X is NP-complete 1.prove X \in nP 2.choose a problem Y that is known to be NP-complete 3.Prove that Y≤pX