ptime (657B)
1 # PTIME 2 3 [ptime_complete] 4 5 When the input consists of integers, we distinguish: https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time 6 - "strongly polynomial" which means 7 - polynomial in the number of inputs 8 - the memory used in polynomial in the size of the input 9 - "weakly polynomial" meaning polynomial in the number of integers and in the log of integers, e.g., [euclidean_algorithm], not just polynomial in the number of integers 10 - not to be confused with [pseudo_polynomial_time]!! 11 12 Up: [complexity_class] 13 14 See also: [pseudo_polynomial_time], [quasipolynomial], [oplusp], [ptime_reduction] 15 16 Aliases: P, polynomial time