Difference between NP-hard and NP-complete problems

-
Let us take two problems A and B both are NP problems.
  • Reducibility - If we can convert one instance of a problem A into problem B (NP problem) then it means that A is reducible to B.
  • NP-hard - Now suppose we found that A is reducible to B, then it means that B is at least as hard as A.
  • NP-Complete - The group of problems which are both in NP and NP-hard are known as NP-Complete problem.
P is set of problems that can be solved by a deterministic Turing machine in Polynomial time.
NP is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time. P is subset of NP

Comments

Post a Comment

Popular posts from this blog

Asymptotic notations

-
  Data Structure The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on machine specific constants,  and doesn’t require algorithms to be implemented and time taken by programs to be compared. Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.  The following 3 asymptotic notations are mostly used to represent time complexity of algorithms. 1) Θ Notation, 2) Big O Notation, 3) Ω Notation. Click here to learn more
Read more
-
  STACKS in Data Structure A stack is  an abstract data type that holds an ordered, linear sequence of items . In contrast to a queue, a stack is a last in, first out (LIFO) structure. A real-life example is a stack of plates: you can only take a plate from the top of the stack, and you can only add a plate to the top of the stack... Click here to Know more
Read more

Array

-
Image
  An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number. For instance, if we want to store the marks scored by a student in 5 subjects, then there’s no need to define individual variables for each subject. Rather, we can define an array which will store the data elements at contiguous memory locations. · array  marks[5]  defines the marks scored by a student in 5 different subjects where each subject marks are located at a particular location in the array i.e.  marks[0]  denotes the marks scored in first subject,  marks[1]  denotes the marks scored in 2nd subject and so on.
Read more