A formula of length n can have at least
sqrt(n) different variables. It is satisfiable if some assignment
of values to those variables makes it true. But there are
2sqrt(n) assignments of values to the variables, and
trying them all takes at least 2sqrt(n) steps. Since
2sqrt(n) grows faster than any polynomial, SAT is not
solvable in polynomial time. So SAT is not in P. But SAT is in NP,
so P and NP are clearly different classes.
Problem 1. The input consists of three integers
a, b and c. The question is, do there exist
positive integers x and y such that
ax2 + by = c?
Problem 2. The input consists of two integers
aand c. The question is, does there exist
a positive integer x such that
ax2 = c?
Problem 2 has efficient algorithms, but no efficient algorithm
is known for problem 1. How, in general terms, might you go about
identifying a problem that is difficult to solve, and distinguish it
from a problem that is easy to solve?