P versus NP
If a proposed answer can be checked quickly, can it also be found quickly? Formally: is every problem in NP also in P?
This problem has no runnable starter yet. Use the suggested experiments below as a starting point in the editor. Open the editor
Suggested experiments
-
Brute-force SAT and its growth
Write a checker for a CNF formula and a brute-force search over all assignments. Measure how the running time grows with the number of variables.
Establishes: Measured running times of your implementation on your inputs.
Does not establish: Any lower bound for every possible algorithm.
-
Verify versus solve
For subset sum or graph colouring, time how long it takes to check a given certificate and how long it takes to find one.
Establishes: The gap between checking and searching for your implementations.
Does not establish: That the gap is unavoidable.