Explore mathematical questions and the work around them.

23 problems

Can every decision problem with polynomially bounded, polynomial-time-checkable certificates also be decided in deterministic polynomial time?

Theoretical computer scienceper Clay · P versus NPchecked