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.

Ancestors (5)

  1. Unsolved problems in mathematics
  2. Mathematical problems
  3. History of mathematics
  4. Mathematics
  5. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version