Reductions among polynomial isomorphism types

DOI10.1016/0304-3975(85)90139-2zbMath0595.03042OpenAlexW2051433988MaRDI QIDQ1077412

B. George

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90139-2

zbMATH Keywords

polynomial reductioncountable partial orderingNP-complete setpolynomial many-one degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (17)

Some remarks on witness functions for nonpolynomial and noncomplete sets in NP ⋮ Scalability and the isomorphism problem ⋮ Query-monotonic Turing reductions ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ Isomorphisms and 1-L reductions ⋮ Collapsing degrees ⋮ On the complexity of graph reconstruction ⋮ A survey of one-way functions in complexity theory ⋮ Gap-languages and log-time complexity classes ⋮ Productive functions and isomorphisms ⋮ New developments in structural complexity theory ⋮ On sets polynomially enumerable by iteration ⋮ On p-creative sets and p-completely creative sets ⋮ Polynomial-time compression ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ On the p-isomorphism conjecture ⋮ Padding, commitment and self-reducibility

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cook reducibility is faster than Karp reducibility in NP
• Oracle-dependent properties of the lattice of NP sets
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• A note on natural complete sets and Goedel numberings
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• On the density of honest subrecursive classes
• On log-tape isomorphisms of complete sets
• A Note on Sparse Complete Sets
• Sparse Sets in : Relativizations
• Completeness, Approximation and Density
• The honest subrecursive classes are a lattice
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Simple Goedel Numberings and Translations
• Degrees of Unsolvability. (AM-55)
• Linear orderings under one-one reducibility
• A note on dense and nondense families of complexity classes
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Reductions among polynomial isomorphism types