Assertion: algorithm | /r/CapableOf | run in polynomial time
Facets:
value: strongly
type: DEGREE
value: depending on the choices
type: OTHER
value: under one model
type: OTHER
Source sentences:
text: An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in weakly polynomial time.
text: (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.)
text: An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.
text: The algorithm runs in strongly polynomial time if