A nonapproximability result for finite function generation

DOI10.1016/S0020-0190(97)00112-9MaRDI QIDQ287157zbMATH OpenOpenAlexFDO

Authors Peter Jonsson

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00112-9

zbMATH Keywords

computational complexityapproximationfunction generationPSPACE

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 4043835
• On the complexity of finite random functions
• Genericity, Randomness, and Polynomial-Time Approximations
• scientific article; zbMATH DE number 2159650
• scientific article; zbMATH DE number 3884099
• Toxicology of nanoparticles
• On the complexity of discrete generation problems
• Complexity of short generating functions
• A finite set of functions with an EXPTIME-complete composition problem
• scientific article; zbMATH DE number 741349

Cites work

• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 1332658 (Why is no real title available?)
• Approximate formulas for some functions of prime numbers
• Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)

Cited in

(1)

• Impossibility of finite generation of partial recursive functions by a unary isotone operation

This page was built for publication: A nonapproximability result for finite function generation

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