17.8. Conjectures


Computability

Diagonalization shows that K is not computable. It is easy to show that K is partially computable. So

There exists a problem that is partially computable but not computable.

Polynomial time and space

Although diagonalizations can be carried out for complexity classes, it is not sensitive enough to prove that there is a problem in NP that is not in P.

We do not even know how to prove that there is a problem in PSPACE that is not in P.

That forces us to resort to conjectures. The following are some standard conjectures.

You should be aware of the standard conjectures.