On isomorphisms and density of NP and other complete sets

L Berman, J. H. (1977). On isomorphisms and density of NP and other complete sets.

Type

Unclassified

Intellectual base

Unclassified

Year

1977

DOI

10.1137/0206023

Link

https://doi.org/10.1137/0206023

Cited by

1 citation across 1 artifact.

Domain-specific

• Berman–Hartmanis conjecture
  • The isomorphism conjecture claims NP-complete sets share one polynomial-time structural shape, is supported for paddable complete sets, and is challenged by relativized worlds, one-way-function assumptions, and sparse or artificial completeness constructions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:c7cc171d05b6 · see in the full table