Constructivizing Membership Proofs in Complexity Classes

DOI10.1142/S0129054197000276MaRDI QIDQ4385199zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind

Publication date 27 July 1998

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054197000276

zbMATH Keywords

polynomial-time algorithmself-witnessing property

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Self-witnessing polynomial-time complexity and prime factorization
• Constructive complexity
• Some results on selectivity and self-reducibility
• Using self-reducibilities to characterize polynomial time

Cited in

(3)

• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• A note on the self-witnessing property of computational problems
• Self-witnessing polynomial-time complexity and prime factorization

This page was built for publication: Constructivizing Membership Proofs in Complexity Classes

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