Problems {P problem} can be solvable with polynomials {polynomial time}| {P time}. Time to solve them increases as polynomial-first-term power, as number of items grows. Linear growth has power one: n^1. Quadratic growth has power two: n^2. Cubic growth has power three: n^3.
Polynomial-time problems include whether number is prime or not, if two lists have all members paired, and if all towns on maps have paths to other towns.
exponential
Problems {non-deterministic problem} {NP problem} can grow superpolynomially or exponentially in time, resources, or memory {non-deterministic polynomial time} {NP time}, as number of items grows. NP problems include all P problems.
Konigsburg bridges problem is an NP problem. Superpolynomial problems {subset sum problem} can try to find sets of numbers that add to zero from a large number set. Can a set of boxes fit in a larger box? Do three-color maps have no neighboring countries with same color?
Evaluating proposed solutions to NP problems requires polynomial time.
NP-complete
NP problems {non-deterministic polynomial time complete} {NP-complete} can be the most general. NP-complete problems include all NP problems. Quantum computers cannot solve NP-complete problems in P time, but can solve some NP problems in much faster NP time, by using specific problem features.
Mathematical Sciences>Computer Science>Software>Algorithm>Polynomial
3-Computer Science-Software-Algorithm-Polynomial
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0224