NP Complete
How is Q an NP-Complete problem?
The traveling salesman
problem consists of a salesman and a group of cities. The salesman has to visit
every of the cities starting from a certain one (e.g. the hometown) and
returning to the same cityitself. The challenge of the problem is that the traveling
salesman wants to minimize the total length of the trip.
To find a clique of G:
A Hamiltonian cycle is a cycle in a graph passing through all the vertices once.
Vertex Cover:
Given a graph and integer k, Is there a set of k vertices such that each of the graph is at least connected to one of the vertices in the set. More generally the problem is stated as: Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.
Though the problem is NP complete, it can be solved in polynomial time for following types of graphs.
What Is P type?
P-
Polynomial time-solving. Problems that can be solved in polynomial time, which
take time like O(n), O(n2), O(n3). Eg: finding a maximum element in an array or
to check whether a string is a palindrome or not. so there are many problems
that can be solved in polynomial time.
What Is NP-Complete?
“NP-Complete”
comes from Non Deterministic Polynomial Complete - “Solve one, Solve them all”.
A problem x that is in NP is also in NP-Complete if and only if every other
problem in NP can be quickly (ie. in polynomial time) transformed into x. In
other words:
• x is in NP, and
• Every problem in NP is reducible to x
•So what makes NP-Complete so
interesting is that if anyone of the NP-Complete problems was to be solved
quickly then all NP problems can be solved quickly.
CNF Satisfiability Problem
Fact Time: There are more NP-Complete problems than provably intractable problems.
What is NP-Hard?
NP-Hard is the problem that is
at least as hard as the hardest problems in NP. Note that NP-Complete problems
are also NP-hard. However not all NP-hard problems are NP (or even a decision
problem), despite having 'NP' as a prefix. That is the NP in NP-hard does not
mean 'non-deterministic polynomial-time'. Yes this is confusing but its usage
is entrenched and unlikely to change.
To get famous in a
hurry, for any NP-complete problem:
- Raise the lower bound (via a
stronger proof)
- Lower the upper bound (via a better
algorithm)
Is it P=NP or P != NP?
Here we come to the 1960s most
important unanswered questions!!
Many optimization problems
appear amenable only to brute force. The classes of problems which are
respectively known and not known to have good algorithms are of great
theoretical Interest algorithms for the travelling salesman problem. My reasons
are the same as for any mathematical conjecture:
(1) It's a legitimate
mathematical possibility, and
(2) I do not know.
How can we make progress on this
problem?
1. We could find an
algorithm for every NP problem
2. We could use
polynomial-time reductions to find the toughest problems and just work on
those.
Fact Time: These Hardest NP
problems turned out to be called as NP COMPLETE afterward!
Reducibility
If some
problem A can be converted into problem
B (NP problem) then it means that A is reducible to B. So the possibility of A
to be converted is called Reducibility.
How is Q an NP-Complete problem?
1. Q is in NP
2. Every other NP problem
polynomial-time reducible to Q
The
problem lies in finding the minimal path passing from all vertices at once. For
example, the path Path1 {A, B, C, D, E, A} and the path Path2 {A, B, C, E, D,
A} pass all the vertices but Path1 has a total length of 24 and Path2 has a
total length of 31.
Thus Traveling salesman
problem is NP complete!
5-Clique:
Suppose that G is
an undirected graph. Say that a set S of vertices of G form a
clique if each vertex in S is adjacent to each other vertex in S.
5 Clique problem states that given an undirected graph, does that graph have a
clique of size at least 5.
1. Suppose that G has n
vertices.
3. If the degree of v
is n − 1, stop; G is a clique, so the largest clique in G
has size n.
4.
Otherwise, remove v and all of its edges from G.
Find the largest clique in the smaller graph. Report that as the largest clique
in G.
The algorithm above does not work. You can find a counterexample,
where the algorithm removes a vertex that is part of the largest
clique. Clique problem is NP complete.
The algorithm above does not work. You can find a counterexample,
where the algorithm removes a vertex that is part of the largest
clique. Clique problem is NP complete.
Hamilton Path:
A Hamiltonian cycle is a cycle in a graph passing through all the vertices once.
P = {A, B, C, D, E} is a
Hamiltonian cycle.
The problem of finding a Hamiltonian cycle in a graph is NP-complete.
The problem of finding a Hamiltonian cycle in a graph is NP-complete.
Map Colouring:
When you colour a map the goal is to give neighbouring regions different colours so that you can see their common borders clearly while minimizing visual distraction by using only a few colours. No more than four colours are needed to shade the regions on any map in such a way that adjoining regions are distinguished by colour.
When you colour a map the goal is to give neighbouring regions different colours so that you can see their common borders clearly while minimizing visual distraction by using only a few colours. No more than four colours are needed to shade the regions on any map in such a way that adjoining regions are distinguished by colour.
Vertex Cover:
Given a graph and integer k, Is there a set of k vertices such that each of the graph is at least connected to one of the vertices in the set. More generally the problem is stated as: Given an undirected graph, the vertex cover problem is to find minimum size vertex cover.
Though the problem is NP complete, it can be solved in polynomial time for following types of graphs.
1) Bipartite Graph
2) Tree Graph
Conclusion
The next time you see an NP Problem, you know that after reading our blog conceptually you will have No Problem : ) !!
References
[3]https://www.britannica.com/science/algorithms
