Algo-Amaze!: Algo-Amaze NP-Complete

NP Complete

Introduction

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.

Algo-amaze time! :

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?

Q is NP-Complete if:

1. Q is in NP

2. Every other NP problem polynomial-time reducible to Q

Travelling Salesman 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.

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.

To find a clique of G:

1. Suppose that G has n vertices.

2. Find a vertex v of the smallest possible degree in G.

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.

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.

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.

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.