NP-hard problem
An NP-hard problem is a computational problem to which every problem in NP can be reduced in polynomial time, whether or not the problem itself belongs to NP.
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.
- How it is used
- Frames difficult search and optimization tasks where practical computation favors approximate or heuristic solutions.
- 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.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
An 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.
- How it is used
- Frames the traveling salesman problem as a practical demonstration of rapidly growing computational difficulty.
- How deep it goes
- Explains the definition through a brute-force Swift implementation, but does not develop alternative optimization methods.
- Examples
- Uses five Vermont cities, a distance table, recursive permutations, and a 318-mile shortest cycle.
- What you can do after
- Build it from scratch in Swift by generating candidate cycles, measuring routes, and selecting the minimum.
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.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.