NP-hard problem

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

The class of problems at least as hard as the hardest problems in NP, whether or not they are decision problems in NP.

An NP-hard problem is at least as hard as the hardest problems in NP-complete, whether or not it is itself a decision problem. Exact efficient algorithms are generally difficult to find, so practical solutions often use approximation or heuristic solvers. section 2.1.1

The surrounding complexity classes clarify what NP-hard means:

• P contains decision problems solvable in polynomial time by deterministic algorithms. section 2.1.1
• NP problems may be difficult to solve but have solutions that can be verified in polynomial time. section 2.1.1
• NP-complete problems are both NP-hard and verifiable in polynomial time. section 2.1.1

Route selection and clustering

A traveling-salesman route through 13 cities requires selecting the best path according to distance, time, or another criterion. Similar combinatorial growth appears when grouping objects into clusters or organizing smart-cart collection points. section 2.1.1

Problem classes based on hardness and completeness. Problems can be categorized into NP-hard, NP-complete, NP, or P.

Use the problem-class diagram to compare P, NP, NP-complete, and NP-hard categories. section 2.1.1

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Defines NP-hardness, distinguishes neighboring complexity classes, and stops short of presenting formal reductions or proofs.

Examples

Uses traveling-salesman routing, object clustering, smart-cart collection, permutations, combinations, and Stirling numbers.

What you can do after

Evaluate whether an optimization task calls for exact, approximate, or heuristic solving.

How it connects

Connects NP-hardness with P, NP, NP-complete, approximation, heuristic solvers, combinatorial problems, clustering, and the traveling-salesman problem.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Classic Computer Science Problems in Swift: Essential techniques for practicing programmersAn NP-hard problem is a problem at least as difficult as every problem in NP under polynomial-time reductions and not known to have a polynomial-time solution.

Compare how 2 books explain NP-hard problem →

Related concepts

• np-complete problemincludes · An NP-complete problem is a decision problem in NP to which every problem in NP can be reduced in polynomial time.
• Traveling Salesman problemincludes · The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
• approximation algorithmaddressed by · An approximation algorithm computes a feasible solution to an optimization problem and provides a bound or guarantee on its quality relative to an optimal solution.
• linear time complexitycontrasts with · Linear time complexity is an asymptotic running-time growth rate proportional to input size, or to the combined sizes of multiple inputs, up to a constant factor.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.