Polynomial time

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

A computational-time bound that grows no faster than a polynomial function of input size.

Polynomial time describes an algorithm whose running time or computational cost grows according to a polynomial function of input size. Problems solvable in polynomial time are generally called tractable. section 2.1.1

Traveling salesperson problem

For the traveling salesperson problem, input size can be measured by the number of cities to visit. Finding an optimal route illustrates why feasible search spaces and computational cost matter. section 2.1.1

Polynomial time helps distinguish major problem classes:

• P contains decision problems solvable in polynomial time by deterministic algorithms. section 2.1.1
• NP problems have solutions that are hard to find but easy to verify in polynomial time. section 2.1.1
• NP-complete problems are both NP-hard and verifiable in polynomial time; NP-hard problems commonly use approximation or heuristic solvers. 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 classification figure to compare P, NP, NP-complete, and NP-hard problem categories. section 2.1.1

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

How deep it goes

Defines polynomial growth and relates it to P, NP, NP-complete, and NP-hard classifications without deriving complexity bounds.

Examples

Uses traveling salesperson routing, clustering, and a problem-classification figure to ground computational complexity.

What you can do after

Evaluate whether a problem belongs to a tractable class and recognize when approximation or heuristic methods may be appropriate.

How it connects

Connects polynomial time with decision problems, tractability, P, NP, NP-completeness, NP-hardness, approximation, and heuristics.

liveBookmanning.com

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

Related concepts

• np-complete problemcontrasts with · An NP-complete problem is a decision problem in NP to which every problem in NP can be reduced in polynomial time.

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.