Scalability and the isomorphism problem

DOI10.1016/0020-0190(95)00204-9zbMath0875.68542OpenAlexW2011388976MaRDI QIDQ1351582

Judy Goldsmith, Homer, Steven

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00204-9

zbMATH Keywords

Computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Recursion-theoretic ranking and compression ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Tally NP sets and easy census functions.

Cites Work

• Unnamed Item
• On the complexity of ranking
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On sets polynomially enumerable by iteration
• Polynomial-time compression
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Polynomial Time Enumeration Reducibility
• P-Printable Sets
• Toward a Theory of Enumerations

This page was built for publication: Scalability and the isomorphism problem