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.
Friday 25 October 2013
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
- its solution comes from a finite set of possibilities, and
- 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:
- The first stage is a guessing stage that uses choose() to find a solution to the problem.
- 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
(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.
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.
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-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 ).
Subscribe to:
Posts (Atom)