Polynomial Time Enumeration Reducibility

DOI10.1137/0207035MaRDI QIDQ4167585zbMATH OpenOpenAlexFDO

Authors Alan L. Selman

Publication date 1978

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0207035

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25)

Cited in

(17)

• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• Optimization problems and the polynomial hierarchy
• On sets polynomially enumerable by iteration
• Logarithmic advice classes
• Strong nondeterministic Turing reduction - a technique for proving intractability
• A taxonomy of complexity classes of functions
• Scalability and the isomorphism problem
• Competing provers yield improved Karp-Lipton collapse results
• Collapsing degrees via strong computation
• A survey of one-way functions in complexity theory
• On the complexity of graph reconstruction
• The consequences of eliminating NP solutions
• Complete sets and closeness to complexity classes
• Promise problems and access to unambiguous computation
• Polynomial-time axioms of choice and polynomial-time cardinality
• A note on degrees of presentation of games as relational structures

This page was built for publication: Polynomial Time Enumeration Reducibility

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