11 How much harder is solving as compared to just verifying ?

• $\mathbf{P}$: the class of problems which we can solve in polynomial time
• $\mathbf{NP}$ : the class of problems where we can verify a potential solution / answer in polynomial time
• Clearly, $\mathbf{P}\subseteq \mathbf{NP}$
  • Solving is a (hard) way of verifying (Informal way of saying)
• What about other direction ?
• If we can verify potential solutions for a problem in $n^{1}2$ time then can we solve the problem in
  • $n^{12}$ time
  • $n^{1000000}$ time
  • $n^{100000000000000000000000}$ time
  • $\cdots$

Is solving much much harder than verifying ?

Is $\mathbf{P}=\mathbf{NP}$, or $\mathbf{P}\ne \mathbf{NP}$?

• If you believe $\mathbf{P}=\mathbf{NP}$
  • Try to reason how you can use verification procedure to solve a problem (with only polytime blow-up)
• If you believe $\mathbf{P}\ne \mathbf{NP}$
  • Try to come up with a problem which can be verified efficiently, but cannot be solved efficiently
• We don’t know the answer!