Np-complete problem
An NP-complete problem is a decision problem in NP to which every problem in NP can be reduced in polynomial time.
Optimization Algorithms: AI techniques for design, planning, and control problems
The class of decision problems that are in NP and are at least as hard as every problem in NP.
- How it is used
- Classifies decision problems by whether solutions are efficiently solvable, verifiable, or computationally hard.
- How deep it goes
- Defines NP-completeness through NP-hardness and polynomial-time verification, without developing formal proofs or exact algorithms.
- Examples
- Uses a 13-city traveling-salesperson route and combinatorial clustering as practical illustrations of large search spaces.
- What you can do after
- Evaluate whether exact search is practical and consider approximation or heuristic solvers for difficult optimization problems.
Advanced Algorithms and Data Structures
A decision problem that belongs to NP and is at least as hard as every problem in NP under polynomial-time reductions.
- How it is used
- Frames explosive search as a signal to seek constraints, dynamic programming, or a reformulated problem.
- How deep it goes
- Defines verification and search difficulty, then applies them to knapsack without proving reductions or complexity-class theory.
- Examples
- Uses launch-cargo packing with 62 items, 1,000-kilogram capacity, exhaustive subsets, dynamic programming, and fractional greedy packing.
- What you can do after
- Evaluate/understand when exhaustive search is infeasible and select dynamic programming or greedy reformulation for knapsack variants.
Read how Advanced Algorithms and Data Structures explains np-complete problem →
Related concepts
- graph coloringincludes · Graph coloring is the assignment of colors to graph elements subject to constraints, such as requiring adjacent vertices to have different colors.
- knapsack problemincludes · The knapsack problem is an optimization problem that selects items subject to a capacity constraint to maximize their combined value.
- 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.
- NP-hard problemkind of · 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.
- polynomial timecontrasts with · A polynomial-time algorithm has worst-case running time bounded by a polynomial function of the input size.
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.