Minimization and NP multifunctions

DOI10.1016/J.TCS.2003.10.020MaRDI QIDQ1827394zbMATH OpenOpenAlexFDO

Authors Norman Danner, Chris Pollett

Publication date 6 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2003.10.020

zbMATH Keywords

Implicit computational complexityMinimizationNon-deterministic partial multifunctionsSafe 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

• Safe Weak Minimization Revisited
• scientific article; zbMATH DE number 512846
• Oracles That Compute Values
• scientific article; zbMATH DE number 806743
• Cobham recursive set functions

Cites work

• A new recursion-theoretic characterization of the polytime functions
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4049046 (Why is no real title available?)
• scientific article; zbMATH DE number 4115977 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)

Cited in

(5)

• More complicated questions about maxima and minima, and some closures of NP
• MNP: A class of NP optimization problems
• Safe Weak Minimization Revisited
• HYPER-MINIMIZATION IN O(n²)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)

This page was built for publication: Minimization and \(\mathbf{NP}\) multifunctions

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