Home » Algorithms

P and NP problems and solutions | Algorithms



In this article, we learn about the concept of P problems, NP problems, NP hard problems and NP complete problems.
Submitted by Shivangi Jain, on July 29, 2018

P Problems

P is the set of all the decision problems solvable by deterministic algorithms in polynomial time.

NP Problems

NP is the set of all the decision problems that are solvable by non - deterministic algorithms in polynomial time.

Since deterministic algorithms are just the special case of non - deterministic ones, so we can conclude that P is the subset of NP.

P and NP problems

Relation between P and NP

NP Hard Problem

A problem L is the NP hard if and only if satisfiability reduces to L. A problem is NP complete if and only if L is the NP hard and L belongs to NP.

Only a decision problem can be NP complete. However, an optimization problem may be the NP hard. Furthermore if L1 is a decision problem and L2 an optimization problem, then it is possible that L1 α L2. One can trivially show that the knapsack decision problem reduces to knapsack optimization problem. For the clique problem one can easily show that the clique decision problem reduces to the clique optimization problem. In fact, one can also show that these optimization problems reduce to their corresponding decision problems.

P, NP and HNP problems

NP Completeness Problem

Polynomial time reductions provide a formal means for showing that one problem is at least as hard as another, within a polynomial time factor. This means, if L1 <= L2, then L1 is not more than a polynomial factor harder than L2. Which is why the “less than or equal to” notation for reduction is mnemonic. NP complete are the problems whose status are unknown.

Some of the examples of NP complete problems are:

1. Travelling Salesman Problem:

Given n cities, the distance between them and a number D, does exist a tor programme for a salesman to visit all the cities so that the total distance travelled is at most D.

2. Zero One Programming Problem:

Given m simultaneous equations,

Zero One Programming Problem

3. Satisfiability Problem:

Given a formula that involves propositional variables and logical connectives.

A language L is the subset [0, 1]* is NP complete if,

  1. L belongs to NP and
  2. L' ← L for every L' belongs to NP

All NP complete problems are NP hard, but some NP hard problems are not known to be NP complete.

If NP hard problems can be solved in polynomial time, then all the NP complete problems can be solved in polynomial time.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Quick links
Latest articles, Internship, Members
New...
Coding problems, Algorithms, Discrete Mathematics, Big data
Languages
C, C++, C++ STL, Java, Data Structure, C#.Net, Android, Kotlin, SQL
Web
PHP, Python, JavaScript, CSS, Ajax, Node.js, Web prog.
Programs
C, C++, DS, Java, C#, Python
Aptitude
C, C++, Java, DBMS
Interview
C, Embedded C, Java, SEO, HR
CS Subjects
CS Basics O.S. Networks DBMS Embedded Systems Cloud Computing Machine learning CS Organizations Linux DOS
More...
Articles, Puzzles, News/Updates


Recommended posts
C Tips & Tricks, C++ Tips & Tricks
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distros of 2018
C programming optimization techniques
Differences b/w C & Embedded C?
Embedded C Interview Q. & A.
C programming tips for Embedded Development
Basic rules of writing a C program
Important points (rules) to remember while writing C/C++ program
Top 5 Websites for solving programming challenges
Read more...


Others...
Computer G.K. (MCQ)
Most viewed pages...
Categories...



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.