Friday 25 October 2013

NP COMPLETE PROBLEMS

What is NP-Complete?
Informally, these are the hardest problems in
the class NP.
If any NP-complete problem can be solved by a
polynomial time deterministic algorithm, then
every problem in NP can be solved by a
polynomial time deterministic algorithm
But no polynomial time deterministic algorithm
is known to solve any of them.

Examples of NP-complete problems
• Traveling salesman problem
• Hamiltonian cycle problem
• Clique problem
• Subset sum problem
• Boolean satisfiability problem
• Many thousands of other important
computational problems in computer science,
mathematics, economics, manufacturing,
communications, etc.

SAT (Boolean satisfiability)
In order to use polynomial-time reductions to show
that problems are NP-complete, we must be able to
directly show that at least one problem is NPcomplete,
without using a polynomial-time reduction
Cook proved that the the Boolean satisfiability
problem (denoted SAT) is NP-complete. He did not
use a polynomial-time reduction to prove this.
This was the first problem proved to be NP-complete.

Tuesday 22 October 2013

NP COMPLETE PROBLEM


Definition of NP
  • Definition 1 of NP: A problem is said to be Non deterministically Polynomial (NP) if we can find a non deterministic Turing machine that can solve the problem in a polynomial number of non deterministic moves.
  • For those who are not familiar with Turing machines, two alternative definitions of NP will be developed.
  • Definition 2 of NP: A problem is said to be NP if
    1. its solution comes from a finite set of possibilities, and
    2. it takes polynomial time to verify the correctness of a candidate solution
  • Remark: It is much easier and faster to "grade" a solution than to find a solution from scratch.
  • We use NP to designate the class of all non deterministically polynomial problems.
  • Clearly, P is a subset of NP
  • A very famous open question in Computer Science:
P = NP ?
  • An NP algorithm is an algorithm that has 2 stages:
    1. The first stage is a guessing stage that uses choose() to find a solution to the problem.
    2. The second stage checks the correctness of the solution produced by the first stage. The time of this stage is polynomial in the input size n.

KNAPSACK  PROBLEM
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

The problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatorics,computer science,complexity theory, cryptography and applied mathematics.

The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. It is not known how the name "knapsack problem" originated, though the problem was referred to as such in the early works of mathematician Tobias Dantzig (1884–1956), suggesting that the name could have existed in folklore before a mathematical problem had been fully defined.
A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem.

Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman knapsack cryptosystem.


  • The goal is to maximize the value of a knapsack that can hold at most W units (i.e. lbs or kg) worth of goods from a list of items I0, I1, … In-1.
  •       Each item has 2 attributes:
1)      Value – let this be vi for item Ii
2)      Weight – let this be wi for item Ii

Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? A multiple constrained problem could consider both the weight and volume of the boxes.
(Solution: if any number of each box is available, then three yellow boxes and three grey boxes; if only the shown boxes are available, then all but the green box.

The following is pseudo code for the knapsack problem:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w] := 0
end for
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for



 

EULER'S NP COMPLETE PROBLEM

In the summer of 1735 Leonhard Euler (pronounced .Oiler.), the famous Swiss mathematician,was walking the bridges of the East Prussian town of K¨onigsberg. After a while, henoticed in frustration that, no matter where he started his walk, no matter how cleverly he continued, it was impossible to cross each bridge exactly once. And from this silly ambition,the field of graph theory was born.
Euler identified at once the roots of the park's deficiency. First, you turn the map of the
park into a graph whose vertices are the four land masses (two islands, two banks) and whose edges are the seven bridges:








This graph has multiple edges between two vertices.a feature we have not been allowing so far in this book, but one that is meaningful for this particular problem, since each bridge must be accounted for separately. We are looking for a path that goes through each edge exactly once (the path is allowed to repeat vertices). In other words, we are asking this question: When can a graph be drawn without lifting the pencil from the paper?
The answer discovered by Euler is simple, elegant, and intuitive: If and only if (a) the
graph is connected and (b) every vertex, with the possible exception of two vertices (the start and final vertices of the walk), has even degree . This is why K¨onigsberg's park was impossible to traverse: all four vertices have odd degree.
To put it in terms of our present concerns, let us define a search problem called Euler
PATH.

Monday 21 October 2013

NP Complete problem

NP Complete problem
 Introduction:
· There are two types of problems:
 Problems whose time complexity is
polynomial: O(logn), O(n), O(nlogn),
O(n 2), O(n 3)
Examples: searching, sorting, merging,
MST, etc.
 Problems with exponential time
complexity: O(2n), O(n!), O(n n), etc.
Examples: TSP, n-queen, 0/1knapsack,
etc.
· Two classes of algorithms:
 P: The set of all problems, which can be
solved by deterministic algorithms in
polynomial time.
 NP: The set of all problems which can be
solved by nondeterministic algorithms in
polynomial time (NP: Nondeterministic
Polynomial)

CLIQUE PROBLEM
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.
For example, the maximum clique problem arises in the following real-world setting. Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance. To find a largest subset of people who all know each other, one can systematically inspect all subsets, a process that is too time-consuming to be practical for social networks comprising more than a few dozen people. Although this brute-force search can be improved by more efficient algorithms, all of these algorithms take exponential time to solve the problem. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation. Along with its applications in social networks, the clique problem also has many applications in bioinformatics and computational chemistry.
Clique problems include:
finding the maximum clique (a clique with the largest number of vertices), 
finding a maximum weight clique in a weighted graph, 
listing all maximal cliques (cliques that cannot be enlarged) 
solving the decision problem of testing whether a graph contains a clique larger than a given size.
These problems are all hard: the clique decision problem is NP-complete , the problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate, and listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Nevertheless, there are algorithms for these problems that run in exponential time or that handle certain more specialized input graphs in polynomial time.

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-completeis 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 ).