NPHard and NPComplete Problems
NPComplete Problems is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.
NPComplete
 The class of problems “NPcomplete stands for the sublass od decision problems in NP that are hardest.
 The class NPcomplete is abbreviated as NPC and comes from:
 Nondeterministic polynomial
 Complete“Solve one, solve them all”
 A decision problem L is said to be NPComplete if:
 L is in NP that means any given solution to this problem can be verified quickly in polynomial time.
 Every problem is NP reducible to L in polynomial time.
 It means that if a solution to this L can be verified in polynomial time then it can show to be in NP.
 A problem that satisfies the second condition is said to be NPhard that will examined in recent.
 Informally it is believed that if an NPC problem has a solution in polynomial time then all other NPC problems can be solved in polynomial time.

The list given below is the examples of some wellknown problems that are NPcomplete when expressed as decision problems.
 Boolean circuit satisfiability problem(CSAT).
 Npuzzle problem.
 Knapsack problem.
 Hamiltonian path problem.
 Travelling salesman problem.
 Subgraph isomorphism problem.
 Subnet sum problem.
 Clique Decision Problem (CDP).
 Vertex cover problem.
 Graph coloring problem.
 The following techniques can apply to solve NPC problems and they often give rise to substantially faster algorithms:
 Approximation Approach.
 iii. Restriction.
 Parameterization. v. Heuristics.
NPHard
The class NPhard written as NPH or NPH stands for nondeterministic polynomial time hard. The class can define as:
 NPH is a class of problems that are “At least as hard as the hardest problems in NP”
 A problem H is NPhard if there is an NPC problem L that is polynomial time reducible to H (i.e. L H).
 A problem H said to be NPH if satisfiability reduces to H.
 If an NPC problem L can solve in polynomial time by an oracle machine with an oracle for H.
NPhard problems are generally of the following typesdecisions problems, search problems, or optimization problems.
To prove a problem H is NPhard, reduce a known NPhard problem to H.
If an NPH problem can solve in polynomial time, then all NPC problems can also solve in polynomial time. As a result, all NPC problems are NPH, but all NPH problems are not NPC.
Related Terms
ADA Algorithms, String Matching with Finite Automata, Knuth Morris Pratt Algorithm, P and NP Problems
Leave a Reply