liveBook · Manning

Np

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

The complexity class of decision problems whose proposed solutions can be verified in polynomial time.

NP is the complexity class of decision problems whose proposed solutions can be verified in polynomial time. Decision problems return a simple yes-or-no answer. section 2.1.1

Optimization problems can be reframed as NP-style decision questions: does a feasible solution meet the requested optimality or near-optimality criterion? This connects complexity theory with routing and planning. section 2.1.1

Routing as a decision problem

For a traveling-salesperson instance, ask whether a route visiting every city satisfies a chosen distance or time bound. The corresponding optimization task seeks the best route; related vehicle-routing problems assign customers to depot-based vehicles while meeting demand. section 2.1.1

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

How deep it goes
Defines polynomial verification and decision reformulation, then situates NP among broader complexity classes.
Examples
Uses TSP route bounds, CVRP delivery planning, and a Greater Toronto Area city-tour illustration.
What it assumes
Assumes familiarity with algorithms and optimization while defining decision problems and polynomial running time.
What you can do after
Evaluate optimization tasks by converting them into polynomial-verification decision questions.
How it connects
Connects decision problems with polynomial time, optimization, TSP, vehicle routing, P, NP-hard, and NP-complete.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

Compare how 2 books explain np →

Related concepts

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.