Time polynomial in input or output

DOI10.2307/2274767zbMATH Open0692.03026OpenAlexW2140289158MaRDI QIDQ3033752FDOQ3033752

S. 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

Recommendations

• Functions computable in polynomial space
• scientific article; zbMATH DE number 4134023
• A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs
• A new Characterization of Type-2 Feasibility
• scientific article; zbMATH DE number 3958737

zbMATH Keywords

polynomial timebinary stringslength of inputlength of outputupper compositionupper iteration

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)

Cited In (2)

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

This page was built for publication: Time polynomial in input or output

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3033752)