12 P versus NP

• What do must people believe ?
  • $\mathbf{P}$ is not equal to $\mathbf{NP}$
• Why haven’t we able to prove it then ?
  • Hard to rule out all possible polytime algorithms
  • Situation is actually quite embarrassing:
    • SAT can be solved in $2^N\cdot (N+M{)}^{O(1)}$ time
    • Don’t even know how to rule out $1.9999999999^N\cdot (N+M{)}^{O(1)}$