A note on SpanP functions

DOI10.1016/0020-0190(94)00068-9MaRDI QIDQ1328756zbMATH OpenOpenAlexFDO

Authors Meena Mahajan, Thomas Thierauf, N. V. Vinodchandran

Publication date 3 August 1994

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

Full work available at URL https://doi.org/10.1016/0020-0190(94)00068-9

zbMATH Keywords

GapSpanP

Mathematics Subject Classification ID

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

Recommendations

• Gap-definable counting classes
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 4066859
• scientific article; zbMATH DE number 58301
• A very hard log-space counting class

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• On counting and approximation
• PP is as Hard as the Polynomial-Time Hierarchy
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent

Cited in

(6)

• A very hard log-space counting class
• The consequences of eliminating NP solutions
• scientific article; zbMATH DE number 58301 (Why is no real title available?)
• scientific article; zbMATH DE number 4066859 (Why is no real title available?)
• A note on spanning with options
• scientific article; zbMATH DE number 1384937 (Why is no real title available?)

This page was built for publication: A note on SpanP functions

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