Safe Weak Minimization Revisited

DOI10.1137/S0097539701387854MaRDI QIDQ3149881zbMATH OpenOpenAlexFDO

Authors Dieter Spreen

Publication date 29 September 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539701387854

zbMATH Keywords

implicit computational complexityminimizationmultifunctionnondeterministic polynomial timenormal form theoremrecursion on notationsafe recursion

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Minimization and \(\mathbf{NP}\) multifunctions
• scientific article; zbMATH DE number 2110623
• The polynomial hierarchy of functions and its levels
• A new Characterization of Type-2 Feasibility
• scientific article; zbMATH DE number 4139728
• scientific article; zbMATH DE number 4139739
• scientific article; zbMATH DE number 65741
• Function algebraic characterizations of the polytime functions
• scientific article; zbMATH DE number 1223632
• Characterizing PSPACE with pointers

Cited in

(7)

• Minimization and \(\mathbf{NP}\) multifunctions
• A new function algebra of EXPTIME functions by safe nested recursion
• Safe recursive set functions
• scientific article; zbMATH DE number 4115977 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• A recursion-theoretic characterisation of the positive polynomial-time functions
• A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)

This page was built for publication: Safe Weak Minimization Revisited

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