np complete problem

NP-COMPLETE PROBLEM EXAMPLE

NP-COMPLETE PROBLEM

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems. The abbreviation NP refers to "non-deterministic polynomial time."

NP-complete problem, are computational problems for which no efficient solution algorithm has been found. So-called easy, or tractable, problems can be solved by computer algorithms that run in polynomial time; i.e., for a problem of size n, the time or number of steps needed to find the solution is a polynomial function of n. Algorithms for solving hard, or intractable, problems, on the other hand, require times that are exponential functions of the problem size n.

             There is a set of problems in NP for which if there’s a polynomial solution to one there will be a polynomial solution to all. The set is called NP-Complete

The NP-class problems are divided as NP Complete and NP Hard.

·         NP-hard: is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an Np-Complete problem L that is polynomial time Turing-reducible to H.

·         NP-complete: is a class of decision problems  A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems,these problems cannot be solved in the polynomial time.  

Formal definition of NP-completeness

Main article: formal definition for NP-completeness (article P = NP)

A decision problem   is NP-complete if:

1.   is in NP, and

2. Every problem in NP is reducible to   in polynomial time.

 C can be shown to be in NP by demonstrating that a candidate solution to   can be verified in polynomial time.

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.

A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for  , we could solve all problems in NP in polynomial time.

EXAMPLE: Bin packing problem

In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem. There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in removable media and technology mapping in Field-programmable gate array semiconductor chip design.

The bin packing problem can also be seen as a special case of the cutting stock problem. When the number of bins is restricted to 1 and each item is characterized by both a volume and a value, the problem of maximizing the value of items that can fit in the bin is known as the knapsack problem.

 

Offline bin packing:

All n items are known in advance, i.e. before they have to be packed.

Prior to the packing, n and s1, ..., sn are known in advance. An optimal packing can be found by exhaustive search.

Approach to an offline approximation algorithm:

Initially sort the items in decreasing order of size and assign the larger items first.

First Fit Decreasing (FFD) resp. FFNI

Best Fit Decreasing (BFD)

First Fit Decreasing

Lemma 1:

Let I be an input sequence of n objects with sizes

s1 ≥ s2 ≥ ..... ≥ sn

and let m = OPT(I).

Then, all items placed by FFD into bins

Bm+1,Bm+2, ... , BFFD(I)

Are of size at most 1/3.

Lemma 2:

Let I be an input sequence of n objects with sizes

s1 ≥ s2 ≥ ..... ≥ sn

and let m = OPT( I ).

Then the number of items placed by FFD into bins

Bm+1,Bm+2, ... , BFFD(I)

is at most m – 1.

Proof:

Assumption: FFD places more than m – 1 items, say x1,....,xm,

into extra bins.

Theorem:

For all input sequences I :

                     FFD( I ) ≤ (4 OPT( I ) + 1) / 3.

Theorem:

1. For all input sequences I : FFD( I ) ≤ 11/9 OPT( I ) + 4.

2. There exist input sequences I such that: FFD( I ) = 11/9 OPT( I ).