ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT
  • 450 DSA Cracker
  • 5G NR
  • O-RAN

Introduction to P, NP, NP hard, NP Complete

prodevelopertutorial August 18, 2019

In this tutorial we shall learn about what is P, NP, NP hard, NP Complete problems.

This is a complex topic. I have tried my best to make you understand in a easy way.

First, full form of P and NP.

 

P -> Polynomial Time

NO -> Non deterministic Polynomial Time.

 

Now, what is Polynomial Time?

Before we understand polynomial time, let’s understand constant time and linear time.

Any algorithm is said to take Constant time, if we are able to get the value by doing single operation irrespective of input size. It is written as O(1).

 

For example:

 

  1. Accessing element in an array will always take a constant time irrespective of input size.
  2. If the array is sorted in ascending order, getting the min element is always done in constant time.

 

Linear time: Any algorithm is said to take linear time if the time complexity is O(n). It means, the time consumed will be increased as input size increases.

 

Example;

  1. Accessing min element in an unsorted array. If the min element is at the end of the array, it will take O(n) time. And the time will increase as the input size is increased.

 

Now, Polynomial Time:

 

An algorithm is said to take polynomial time, if the upper bound of a polynomial expression is O(n^k) where k is a constant.

 

Ideally, linear time is a polynomial time where K = 1. Below are some of the algorithms that can be solved in polynomial time.

Linear Search O(n)

Insertion Sort O(n^2)

The above problem can be solved at deterministic polynomial time.

 

Below are some of the algorithms that can be solved in exponential time:

 

Travelling Salesman Problem O(2^n)

Hamiltonian Cycle O(2^n)

0/1 knapsack Problem O(2^n)

 

The above problem cannot be solved in deterministic time. Hence we try to solve it through non deterministic time.

 

So what is meant by deterministic and non deterministic algorithms?

 

An algorithm, where the steps are clearly defined is called as deterministic algorithm.

Example: Bubble sort, quick sort, Linear search.

 

The algorithms that shows different behavior for same input, are called as non deterministic algorithms.

All deterministic algorithm can be solved in polynomial time, but non deterministic algorithms cannot be solved in polynomial time.

Before going to our main topic, let’s understand one more concept.

 

Decision Based Problems:

These are the problems that can be solved with a series of “yes” or “no” based decisions. This kind of problems are known as decision based problems. There might be other kind of problems, but we shall stick to decision based problem for now, so to understand next topic.

 

Now coming to out main topic:

P, NP, NP hard, NP Complete

 

P problem Class: Polynomial time problem:

For these kind of problem, there are efficient algorithms that are designed to solve in polynomial time at the worst case.

So P is a class of decision based problems that can be solved efficiently.

 

NP Problem Class:

For NP class problems, we don’t know how to solve them efficiently. But we try to verify the answer efficiently thus having a proof.

So NP is a class of decision based problems, that can be verified efficiently. It means that there is an algorithm present that can verify the output of the problem.

So P class problems, that can be efficiently solvable.

NP class problems, that can be efficiently verifiable.

 

So most of the time, we hear that P = NP, if and only if, the problem in class P are efficiently verifiable.

 

Now for NP complete and NP hard:

Before going to learn about NP hard and NP complete, we have to understand what is reduction based problem?

If you have a problem “M”, it can be reduced to another problem “N” and that “N” problem can be efficiently solved. These kind of problems are called as reduction based problems.

 

Properties of Reduction based problem:

  1. If A is reducible to B in polynomial time, then A can be solved in polynomial time.
  2. If A is not solved in polynomial time, then it means, B also cannot be solved in polynomial time.

 

NP hard Problem:

A problem is called as NP hard, if all the problems in NP can be reduced to polynomial time. It means if I have a set of problems in P and NP, and they can be reduced in polynomial time, then those set of problems are called as NP based problems.

Introduction to P, NP, NP hard, NP Complete

 

NP complete:

The group of problems what are both NP and NP hard is called as NP Complete Problems.

 

Introduction to P, NP, NP hard, NP Complete

 

The intersection of NP and NP hard set of problems are called as NP complete.

If you have any doubts, please write in the comment section below:

Further Reading:

AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

 

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Follow this blog to learn more about C, C++, Linux, Competitive Programming concepts, Data Structures.

Leave a Reply Cancel Reply

You must be logged in to post a comment.

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2023 ProDeveloperTutorial.com
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept”, you consent to the use of ALL the cookies.
Do not sell my personal information.
Cookie SettingsAccept
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT