The Berman-Hartmanis conjecture is a hypothesis in computational complexity theory that relates to the structure of problems within the complexity classes P and NP. Formulated by Jacob Berman and Richard Hartmanis in the early 1970s, the conjecture posits that every NP-complete problem can be efficiently transformed into any other NP-complete problem in a way that preserves the number of solutions.
Articles by others on the same topic
There are currently no matching articles.