patternMajor
Simple (non-mathematical) definition of polynomial time?
Viewed 0 times
definitionsimplepolynomialnontimemathematical
Problem
Computational Complexity Theory is complex. My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time. This is fine for engineers and mathematicians, but I'm looking for a simple definition of the term, suitable for laypeople.
Obviously there would be subsequent qualifications for different time complexity classes, and time complexity may be more properly a ratio based on the problem size, but again, that's a bit more complex than what I'm looking for here.
- Would it be incorrect to cast polynomial time as "time measured in (computational) operations?"
Obviously there would be subsequent qualifications for different time complexity classes, and time complexity may be more properly a ratio based on the problem size, but again, that's a bit more complex than what I'm looking for here.
Solution
Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size.
Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1.
For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential time, although, as we know, this is wrong on many counts.
Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1.
For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential time, although, as we know, this is wrong on many counts.
Context
StackExchange Computer Science Q#81556, answer score: 40
Revisions (0)
No revisions yet.