Reductions among polynomial isomorphism types

DOI10.1016/0304-3975(85)90139-2zbMATH Open0595.03042OpenAlexW2051433988MaRDI QIDQ1077412FDOQ1077412

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

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

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)

Cites Work

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

Cited In (26)

• Title not available (Why is that?)
• Title not available (Why is that?)
• A survey of one-way functions in complexity theory
• On p-creative sets and p-completely creative sets
• Collapsing degrees
• On the complexity of graph reconstruction
• Polynomial-time compression
• Reductions to Graph Isomorphism
• New developments in structural complexity theory
• 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
• Query-monotonic Turing reductions
• On the p-isomorphism conjecture
• 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
• Title not available (Why is that?)

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)