Structural Complexity Theory

← Back to Domain-Specific Abstractions by Domain

1 domain-specific abstractions whose origin domain is Structural Complexity Theory.

• Berman–Hartmanis conjecture — The conjecture that every pair of NP-complete languages is related by a polynomial-time computable bijection whose inverse is also polynomial-time computable.