Polynomial Time Enumeration Reducibility

DOI10.1137/0207035zbMath0386.68055OpenAlexW1970465162MaRDI QIDQ4167585

Selman, Alan L.

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

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

Related Items (17)

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

This page was built for publication: Polynomial Time Enumeration Reducibility