A note on SpanP functions

DOI10.1016/0020-0190(94)00068-9zbMath0807.68033OpenAlexW2023120157MaRDI QIDQ1328756

N. V. Vinodchandran, Thomas Thierauf, Meena Mahajan

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The consequences of eliminating NP solutions

Cites Work

• The complexity of computing the permanent
• The complexity of combinatorial problems with succinct input representation
• On counting and approximation
• PP is as Hard as the Polynomial-Time Hierarchy
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• Unnamed Item
• Unnamed Item