Reductions among polynomial isomorphism types

DOI10.1016/0304-3975(85)90139-2MaRDI QIDQ1077412zbMATH OpenOpenAlexFDO

Authors 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) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On the isomorphism conjecture for weak reducibilities
• On one-way functions and polynomial-time isomorphisms
• Isomorphisms and 1-L reductions
• Complete Problems and Strong Polynomial Reducibilities
• Polynomial-time isomorphism of 1-L-complete sets

Cites work

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

Cited in

(26)

• scientific article; zbMATH DE number 1559593 (Why is no real title available?)
• scientific article; zbMATH DE number 1860651 (Why is no real title available?)
• On p-creative sets and p-completely creative sets
• A survey of one-way functions in complexity theory
• Collapsing degrees
• On the complexity of graph reconstruction
• Polynomial-time compression
• New developments in structural complexity theory
• Reductions to Graph Isomorphism
• Cook reducibility is faster than Karp reducibility in NP
• Strong Reductions and Isomorphism of Complete Sets
• Productive functions and isomorphisms
• Complete Problems and Strong Polynomial Reducibilities
• Strong isomorphism reductions in complexity theory
• On the p-isomorphism conjecture
• Query-monotonic Turing reductions
• On sets polynomially enumerable by iteration
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Every polynomial-time 1-degree collapses if and only if P = PSPACE
• Scalability and the isomorphism problem
• Gap-languages and log-time complexity classes
• Strong reductions and isomorphism of complete sets
• One-way functions and the nonisomorphism of NP-complete sets
• Isomorphisms and 1-L reductions
• Padding, commitment and self-reducibility
• scientific article; zbMATH DE number 3984574 (Why is no real title available?)

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

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