What
sort of data structures might be relevant to you: trees, heaps, graphs? What is
the running time of the algorithm? All of this is fine if it helps you discover
an acceptably efficient algorithm to solve your problem.
Your
algorithm can solve small problems reasonably efficiently (e.g., n _ 20), and
you can count the running time and bounded by asymptotic notations but for the
really large problems you want to solve, your algorithm will never terminates.
When you analyze its running time, you realize that it is running in
exponential time, perhaps 2n or n! or worse!.
By
the end of 60’s, there was great success in finding efficient solutions too
many combinatorics problems. But there was also a growing list of problems for
which there seemed to be no known efficient algorithmic solutions.
So
they concluded that, these problems are inherently hard to solve and no
algorithmic solutions exist that run under exponential time.
Near
the end of the 1960’s, a remarkable discovery was made. Many problems were
still present who couldn’t be solved in the polynomial time. So researcher
introduced the term NP problem, NP problems are those who can’t be solved
within polynomial time is known as NP problems
Now
the area had been totally changed now the goal is no longer to prove that a
problem can be solved efficiently by presenting an algorithm for it. Instead we
will be trying to show that a problem cannot be solved efficiently.
Up
until now all algorithms we have seen had the property that their worst-case
running time is bounded above by some polynomial in n. A polynomial time
algorithm is any algorithm that runs in O(nk) time. A problem is
solvable in polynomial time if there is a polynomial time algorithm for it.
Note: - we can say
that, a polynomial time problem you must have polynomial time algorithms
All
polynomial time algorithms must be bounded with polynomial time such as O(n2)
Suppose
you have, an algorithm that takes as input a graph of size n and an integer k
and run in O(nk) time.
Is
this a polynomial time algorithm? No, because k is an input to the problem so
the user is allowed to choose k = n, implying that the running time would be
O(nn). O(nn) is surely not a polynomial in n. The
important aspect is that the exponent must be a constant independent of n.
Decision
Problems
Most
of the problems which come into the category of P problem are Decision based
problems such as find the shortest path, dynamic programming etc. In case of NP
problems are problems of NP domains again come into the category of Decision
based Problem
Officially Definition of Decision Based
Problem:-
A problem
is called a decision problem if its output is a simple “yes” or “no” (or you
may this of this as true/false, 0/1, accept/reject.) We will phrase many
optimization problems as decision problems. For example: - Greedy method, D.P.
Complexity
Classes
Officially definition of NP class
Problem:
- The set of all decision based problems come into the categories of NP
Problems who can’t be solved or produced an output within polynomial time but verified in the polynomial time. NP class
contains P class as a subset. NP problems being hard to solve
Note: - The term “NP”
does not mean “not polynomial”. Originally, the term meant “non-deterministic
polynomial. It means according on the one input number of output will be
produced.
Officially definition of P class Problem:
- The
set of decision based problems come into the categories of P Problems who can
be solved or produced an output within polynomial time. P problems being easy
to solve
Officially Definition of Polynomial time: -
if we produce an output according to the given input with in specific amount of
time such as within minute, hours. This is known as Polynomial time
Officially Definition of Non Polynomial
time:
- if we produce an output according to the given input but there are no time
constraints is known as Non Polynomial time. But yes output will definitely
produce but time is not fixed yet
Officially
Definition of NP-hard class: - Here you to satisfy the following
points to come into the category of NP-hard
1 1) If we
could solve this problem in polynomial time, then we could solve all NP
problems in polynomial time
2 2) If
you convert the problem in one form to another form within the polynomial time
Officially
Definition of NP-complete class: - A problem is in
NP-complete, if
1 1)
It is in NP
2 2)
It is NP-hard
Pictorial
representation of all NP classes which includes NP, NP-hard,NP-complete
Polynomial Time
Verification
Before
talking about the class of NP-complete problems, it is important to introduce
the notion of a verification algorithm.
Many problems are hard to solve but they have
the property that it easy to verify the solution if one is provided.
Hamiltonian cycle problem:-
Consider
the Hamiltonian cycle problem. Given an undirected graph G, does G have a cycle
that visits every vertex exactly once? There is no known polynomial time
algorithm for this problem.
Note: - It means you
can’t create a Hamiltonian cycle in a graph with a polynomial time even if
there is no specific path is given for the Hamiltonian cycle with the specific
vertex, even you can’t verify the Hamiltonian cycle within the polynomial time
However,
suppose that a graph did have a Hamiltonian cycle. It would be easy for someone
to convince of this. They would simply say: “the cycle is hv3, v7, v1, …..v13i.
We could then inspect the graph and check that
this is indeed a legal cycle and that it visits all of the vertices of the
graph exactly once. Thus, even though we know of no efficient way to solve the
Hamiltonian cycle problem, there is a very efficient way to verify that given
cycle is indeed a Hamiltonian cycle.
Note: - for the verification in the
Polynomial time of a un directed Hamiltonian cycle graph G. There must be
exact/specific/definite path must be given of Hamiltonian cycle then you can
verify in the polynomial time
Officially Definition of CERTIFICATE: - A
piece of information which contains in the given path of vertex in known as
certificate
Relation of P and NP classes
1 1) P
contains in NP
2 2) P=NP
1 1) Observe
that P contains in NP. In other
words, if we can solve a problem in polynomial time, we can certainly verify
the solution in polynomial time. More formally, we do not need to see a
certificate (there is no need to specify the vertex/intermediate of specific
path) to solve the problem; we can solve it in polynomial time anyway.
2 2) However,
it is not known whether P = NP. It
seems you can verify and produce an output of the set of decision based
problems in NP classes in a polynomial time which is impossible because
according to the definition of NP classes you can just verify the solution
within the polynomial time. So this relation can never be hold
Reductions
Concept: - If the
solution of NPC problem does not exist then conversion from one NPC problem to
another NPC problem within the polynomial time. For this you need the concept
of reduction
If solution of the one NPC problem exist
within the polynomial time then rest of the problem can also give the solution
in polynomial time(but it’s hard to
believe).For this you need the concept of reduction
Example: - Consider the
question: Suppose there are two problems, A and B. You know (or you strongly
believe at least) that it is impossible to solve problem A in polynomial time.
You want to prove that B cannot be solved in polynomial time. So you can
convert the problem A into problem B in polynomial time
Example of
NP-complete problem
NP problem (already given): -
Suppose a DECISION BASED problem is given in which a set of inputs/high inputs
you can get high output.
Criteria to come either in NP-hard or
NP-complete
1 1) The
point to be noted here, the output is already given and you can verify the
output/solution within the polynomial time but can’t produce an output/solution
in polynomial time.
2 2) Here
we need the concept of reduction because when you can’t produce an output of
the problem according to the given input then in case you have to use and
emphasis on the concept of reduction in which you can convert one problem into
another problem
Note1:- If you
satisfy the both points then your problem comes into the category of
NP-complete class
Note2:- If you
satisfy the only 2nd points then your problem comes into the category of
NP-hard class
So
according the given decision based NP problem, you can make the decision in the
form of yes or no. If, yes then you
have to do verify and convert into another problem via reduction concept. If
you are being performed both then decision based NP problem is in NP compete
Here we will emphasis on NPC
CIRCUIT SET: - according to
given decision based NP problem you can design the CIRCUIT and verify a given
mentioned output also within the P time. The CIRCUIT is given below:-
CIRCUIT you have been created in class
Note:- you can
design a circuit and verified the mentioned output within Polynomial time but
remember you can never predict the number of gates which produces the high
output against the set of inputs/high inputs within a polynomial time
So
you verified the output and conversion has been done within polynomial time. So
you are in NPC
SAT (Suitability):- A
Boolean function is said to be SAT if the output for the given value of input
is true/high/1
F=X+YZ (created Boolean
function on the basis of CIRCUIT SET)
These points you have to be performed
for NPC
1 1) CIRCUIT
SET≤SAT
2 2) SAT≤CIRCUIT
SET
1 1) CIRCUIT SET≤SAT:- In
this conversion you have to convert CIRCUIT SET into SET within the polynomial
time as we did it
2 2) SAT≤CIRCUIT SET: -
For sake of verification of an output you have to convert SAT into CIRCUIT SET
within the polynomial time and through the CIRCUIT SET you can get the
verification of an output successfully
Note: - If you
performed both conversion of the decision based NP problem within the
polynomial time as I said earlier you can’t create functions for every circuit
within the polynomial time. It concluded
that SAT also in NPC
3CNF SAT:-
Concept: - In 3CNF SAT,
you have at least 3 clauses and in clauses you will have almost 3 literals or
constants
Such
as: - (X+Y+Z)(X+Y+Z)(X+Y+Z)
You can define as: - (XvYvZ) ᶺ(XvYvZ)ᶺ(XvYvZ)
V=OR
operator
ᶺ=AND
operator
Theses
all the following points need to be considered in 3CNF SAT
To
prove: -
1 1) Concept
of 3CNF SAT
2 2) SAT≤
3CNF SAT
3 3) 3CNF≤SAT
1 1) Concept of 3CNF SAT:- As
I defined earlier in the beginning of topic
2 2) SAT≤3CNF SAT:-
In which firstly you need to convert a Boolean
function created in SAT into 3CNF either in POS or SOP form within the
polynomial time
F=X+YZ
= (X+Y)(X+Z)
=(X+ZZ)(X+YY)
=(X+Y+Z)(X+Y+Z)(X+Y+Z)(X+Y+Z)
=(X+Y+Z)(X+Y+Z)(X+Y+Z)
Proof
of NPC:-
·
It shows that, you can easily convert a
Boolean function of SAT into 3CNF SAT and satisfied the concept of 3CNF SAT
also within polynomial time through Reduction concept.
·
If you want to verify the output in 3CNF
SAT then perform the Reduction and convert into SAT and CIRCUIT ALSO to verify
the output
If you can perform these two points that means 3CNF
SAT also in NPC
[WLECOME TO
NPC]
CLIQUE:-
TO
PROVE: - CLIQUE
is in NPC or not?
For this you have to satisfy the following below
mentioned points: -
1) Definition
of CLIQUE
2) 3CNF≤
CLIQUE
3) CLIQUE≤3CNF≤SAT
4) CLIQUE
belongs to NP
1 1) Definition: - In CLIQUE,
every vertex is directly connected to another vertex and the number of vertices
in the CLIQUE represents the SIZE OF CLIQUE.
As per diagram which you have been
designed in class the SIZE OF THE CLIQUE
=4
2 2)
3CNF≤CLIQUE
Proof: - for
the successful conversion from 3CNF to CLIQUE, you have to follow the two
steps: -
Draw the clause in the form of vertices and each
vertex represents the literals of the clauses
1) They are not compliment to each others
2) They
don’t belong to the same clause
In the conversion, the size of the CLIQUE and
size of 3CNF must be same and you successfully converted 3CNF into CLIQUE within
the polynomial time
3)
CLIQUE≤3CNF
Proof:- As you
know that a function of K clause, there must exist a CLIQUE of size k. It means
that P variables which are from the different clauses can assign the same value
(say it is 1). By using these values of all the variables of the CLIQUES, you
can make the value of each caluse in the function is equal to 1
Example: -
you have Boolean function in 3CNF:-
(X+Y+Z)(X+Y+Z)(X+Y+Z) (i)
After Reduction/conversion from 3CNF to CLIQUE, you
will get P variables such as:- x+y=1, x+z=1 and x=1
Put the value of P variables in equation (i)
(1+1+0)(1+0+0)((1+0+1)
(1)(1)(1)=1 output verified
CLIQUE
belongs to NP:-
Proof: - As
you know very well, you can get the CLIQUE through 3CNF and to convert the
decision based NP problem into 3CNF you have to firstly convert into SAT and
SAT comes from NP.
So
concluded that CLIQUE belongs to NP
Proof
of NPC:-
1) Reduction
achieved within polynomial time from 3CNF to CLIQUE
2) And
verified the output after Reduction from CLIQUE To 3CNF above
So
concluded that, if both Reduction and verification can be done within the
polynomial time that means CLIQUE ALSO IN NPC
VERTEX COVER:-
1 1) VERTEX
COVER definition
2 2)
VERTEX COVER≤CLIQUE≤3CNF
3 3)
CLIQUE≤VERTEX COVER
4 4) VERTEX
COVER belongs to NP
1 1) Definition:-A vertex cover of an undirected graph G=(V,E) defines a set of minimum vertices that covers all the edges directly in E. The size of vertex cover is the number of vertices in it.
i In the vertex cover problem, we wish to determine whether a graph has a vertex cover of given size k
i In the vertex cover problem, we wish to determine whether a graph has a vertex cover of given size k
According to the graph G of vertex cover
which you have been created in class, the size of
VERTEX COVER=2
2 2)
VERTEX
COVER≤CLIQUE
In a graph G of VERTEX
COVER, you have
o
N vertices which contains a VERTEX COVER
K, there must exist of CLIQUE SIZE of size N-K OR
o
In a graph G of vertex cover of N
vertices there must exist a vertex cover of size k and a clique of size N-K
According to the graph G, you have
Number of vertices=6
Size of CLIQUE=N-K=4
You can also create the CLIQUE by complimenting the
graph G of VERTEX COVER means in simpler form connect the vertices in VERTEX
COVER graph G through edges where edges doesn’t exist and remove all the
existed edges
You will get the graph G with CLIQUE SIZE=4
VERTEX
COVER≤ CLIQUE≤ 3CNF:-
After getting the CLIQUE through Reduction in
polynomial time, now you can make the clauses as vertices of CLIQUE graph G and
now you can perform Reduction form CLIQUE To 3CNF and after solving the 3CNF
function in POS form you will get 1/high and output has been verified
3 3)
CLIQUE≤VERTEX
COVER
Here through the Reduction process you can get the
VERTEX COVER form CLIQUE by just complimenting the CLIQUE graph G within the
polynomial time
4 4) VERTEX COVER belongs to NP:-
Proof: - As you know very well, you can get the
VERTEX COVER through CLIQUE and to convert the decision based NP problem into
CLIQUE firstly you have to convert into3CNF and 3CNF into SAT and SAT into
CIRCUIT SET that comes from NP.
Proof
of NPC:-
·
Reduction from CLIQUE to VERTEX COVER
has been done within the polynomial time. In simpler form you can convert into
VERTEX COVER from CLIQUE within the polynomial time
·
And verification has also been done when
you convert VERTEX COVER to CLIQUE and CLIQUE to 3CNF and satisfy/verified the
output within polynomial time also
So it
concluded that Reduction and Verification has been done in polynomial time that
means VERTEX COVER also comes in NPC
SUSET COVER:-
To prove:-
1 1) SUBSET
COVER definition
2 2) VERTEX
COVER≤SUSET COVER
3 3) SEBSET
COVER≤VERTEX COVER
4 4) SUSET
COVER belongs to NP
1 1) SUBSET COVER definition:-
number of subset of edges after making the union for a get all the edges of an undirected graph G=(V,E) and that is called SUBSET COVER
According to the graph G, which you have
been created in class the size of SUBSET COVER=2
V1ȖV4=
{e1,e2,e3,e4,e5,e6} complete set of
edges after the union of vertices
2) VERTEX COVER≤SUBSET COVER
In a
graph G of vertices N, if there exist a VERTEX COVER of size k then there must
also exist a SUBSET COVER of size k also. If you can achieve after the
REDUCTION from VERTEX COVER to SUBSET COVER within polynomial time that means
you did right
3) SUBSET COVER≤VERTEX COVER≤3CNF
Simply
for verification of the output simply perform the Reduction and create CLIQUE
and via equation N-K verify the CLIQUE also and through CLIQUE you can easily
create 3CNF and after solving the Boolean function of 3CNF in polynomial time.
You will get output. It means the output has been verified
4) SUBSET COVER belongs to NP:-
Proof:
- As you know very well, you can get the SUBSET COVER through VERTEX COVER and
VERTEX COVER through CLIQUE and to convert the decision based NP problem into
CLIQUE firstly you have to convert into3CNF and 3CNF into SAT and SAT into
CIRCUIT SET that comes from NP.
Proof of NP-C:-
Reduction
has been successfully done within the polynomial time form VERTEX COVER TO
SUBSET COVER
Output
has also been verified within the polynomial time as you did in the above
conversation
So
concluded that SUBSET COVER also comes
into the category of NPC
No comments:
Post a Comment