Hard promise problems and nonuniform complexity

DOI10.1016/0304-3975(93)90120-IzbMath0778.68035MaRDI QIDQ1261468

Luc Longpré, Selman, Alan L.

Publication date: 16 September 1993

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

zbMATH Keywords

relativizationsself-reducibility\(P\)-selectivity

Mathematics Subject Classification ID

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

Related Items (2)

Space-efficient recognition of sparse self-reducible languages ⋮ A hierarchy based on output multiplicity

Cites Work

• Unnamed Item
• A low and a high hierarchy within NP
• On self-reducibility and weak P-selectivity
• Strong nondeterministic polynomial-time reducibilities
• NP is as easy as detecting unique solutions
• Promise problems complete for complexity classes
• Reductions on NP and p-selective sets
• The ellipsoid method and its consequences in combinatorial optimization
• A comparison of polynomial time reducibilities
• On hiding information from an oracle
• The polynomial-time hierarchy and sparse oracles
• On Circuit-Size Complexity and the Low Hierarchy in NP
• The complexity of promise problems with applications to public-key cryptography
• Sparse Sets, Lowness and Highness
• Complexity Measures for Public-Key Cryptosystems
• Cryptocomplexity and NP-completeness
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Arithmetical Reducibilities I

This page was built for publication: Hard promise problems and nonuniform complexity