Sigfigs: Automatically Solving P vs NP for CSPs

Our program, having just proven that 3-coloring is NP-Hard. Computation time: 0.05s.
Our program, having discovered how to do Gaussian elimination to solve linear equations modulo 3. Computation time: 0.9s.

The elevator pitch

Q: How do you describe every programmer's worst nightmare in two words? A: Exponential runtime.

Consider the job-shop scheduling problem: Given some number of jobs, each of which has a certain processing time, and some number of machines, each of which has a certain processing power, what is the optimal allocation of jobs to machines so that it takes minimal time to compute all jobs? This task sounds simple to automate, but in fact, it is computationally intractable.

The two main computational classes are P, the tractable problems, and NP-Complete, the intractable problems. For a sufficiently large-scale problem, the difference between P and NP might be the difference between 1000 milliseconds and 1000 years of computation time. It is not known whether NP is equal to P; a million-dollar prize is available for the solution of this problem.

Determining whether a given problem is P or NP is often a hard problem. In 2017, the problem was finally solved by Zhuk, who gave a condition to check which would determine how hard a problem is. Checking this condition is usually extremely slow, so no one has ever implemented his algorithm. Until now! By transforming the condition into a very different problem and solving that, our application Sigfigs can solve this problem for CSPs in a under a second, when the simple approach would have taken years.

What it does and how to use it

Given a constraint satisfaction problem (CSP), Sigfigs determines whether it is in P or NP -- and if the problem is tractable (in P), Sigfigs generates source code to solve the problem very efficiently.

To use Sigfigs, follow three simple steps:

1. Convert your problem into a CSP. A CSP instance is a list of variables [x1, …, xn], a list of domains [D1, …, Dn] for each variable, and constraints [C1, …, Cm]. Each variable xi can take on values in Di. Each constraint is a k-ary relation on a subset of [x1, …, xn] of size k, for some constant k. See here for the details.

2. Input the variables and relations into Sigfigs. This can be passed through an API, or through our UI. This means stating what the allowed inputs of each "clause" are.

3. Profit! Sigfigs will output whether the problem is polynomial-time solvable, or if it's NP-Hard. If the problem is polynomial time, Sigfigs will also produce source code that you can use to solve it efficiently. ✌

Limitations of this method

Some problems, like integer factorization, can't be formulated as a CSP. However, a huge number of important problems in computer science and operations research can be formulated as CSPs, for example k-SAT and job-shop scheduling.

The name Sigfigs

The heart of our implementation relies on a mathematical object called a Siggers polymorphism. So Siggers figures out whether the input problem is in P or NP! :)