Time polynomial in input or output

DOI10.2307/2274767zbMath0692.03026OpenAlexW2140289158MaRDI QIDQ3033752

Saharon Shelah, Yuri Gurevich

Publication date: 1989

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274767

zbMATH Keywords

polynomial timebinary stringslength of inputlength of outputupper compositionupper iteration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

On the computational complexity of dynamic graph problems ⋮ On the theory of average case complexity

Cites Work

• Unnamed Item