Skip to main content
Source Link
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

In computational complexity there are several conjectures which are stronger than $NP \ne P$ which have important consequences. To mention a few

  1. The conjecture that factoring is computationally hard is the basis to much theoretical and practical cryptography.

  2. More broadly the conjecture that one-way functions exist has many consequences.

  3. The conjecture that the polynomial hierarchy ($PH$) does not collapse has many consequences.

  4. Khot's unique game conjecture has many important consequences for hardness of approximation.

  5. The exponential time hypothesis ($ETH$)and strong exponential time hypothesis ($SETH$) are strong form of $NP \ne P$ with important consequences.

  6. There are stronger and stronger versions of the "derandomization" conjecture with many consequences.

Post Made Community Wiki by Gil Kalai