Np-complete problem

As explained in 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.

An NP-complete problem is a decision problem that is both NP-hard and verifiable in polynomial time. Its solutions may be difficult to find, but proposed solutions can be checked efficiently. section 2.1.1

Use these classifications to distinguish computational difficulty:

• P contains decision problems solvable in polynomial time by deterministic algorithms. section 2.1.1
• NP contains problems whose solutions are hard to find but easy to verify in polynomial time. section 2.1.1
• NP-hard problems are at least as hard as the hardest NP-complete problems and are commonly approached with approximation or heuristic solvers. section 2.1.1

Traveling salesperson problem

Selecting the best route through 13 cities illustrates the combinatorial search behind practical planning problems. Distance, time, or another criterion can define the preferred route; increasing the number of cities makes exact search difficult. section 2.1.1

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

Compare P, NP, NP-complete, and NP-hard classifications in one visual hierarchy. section 2.1.1

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

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.

How it connects

Connects decision problems with P, NP, NP-hardness, polynomial time, approximation algorithms, heuristic solvers, and TSP.

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
  Advanced Algorithms and Data StructuresA decision problem that belongs to NP and is at least as hard as every problem in NP under polynomial-time reductions.

Compare how 2 books explain 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.

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.