012-2006

MO640 - Multiple-choice question

Regarding computational complexity problem classes, we can say that:

1. NP problems cannot be solved in polynomial time.
2. Any NP problem can be reduced in polynomial time to an NP-complete problem. 
3. There is an intersection between the classes P and NP, which does not completely include any of the two.
4. It has been proved that classes P and NP  are distinct.
5. None of the above.

Original idea by: Tiago Rinck Caveden.
Translation help by: Leandro José de Bortoli.