Constructivizing Membership Proofs in Complexity Classes

DOI10.1142/S0129054197000276zbMATH Open0892.68044OpenAlexW2154884611MaRDI QIDQ4385199FDOQ4385199

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

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

zbMATH Keywords

polynomial-time algorithmself-witnessing property

Mathematics Subject Classification ID

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

Cited In (3)

• Title not available (Why is that?)
• 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)