Asymmetric generation / verification costs

We tend to think that the effort required to generate a solution and verify a solution are roughly equal, assuming that you need to retrace the generation steps to verify that they are correct. But sometimes verification can be far easier than generation [1].

Factoring

For example, suppose I generate two 1000-digit prime numbers, multiply them together, and ask you to recover the two primes by factoring. It takes a split second to verify whether you’ve found the solution, but finding the solution is practically impossible. The security of the internet depends on this fact. (See posts on RSA encryption here.)

Generative AI

Generative AI is notoriously unreliable. But if it’s far easier to verify a solution than to generate it, it’s OK if an AI solution is unreliable. We’ve had several consulting projects lately that amount to evaluating how well an LLM did what it was supposed to do. The LLMs aren’t perfect—no one expected that they would be—but the tasks is to estimate whether the error rate is acceptable.

Differential equations

George Pólya once said “In order to solve a differential equation you look at it till a solution occurs to you.” He was only half joking. Differential equations courses present solution techniques without justification [2], but the solutions can be justified even if they techniques cannot: stick the solution in to the equation and see whether it works.

Finding primes

For the last 70 years, the largest known prime has been a Mersenne prime, with one exception [3]. This is because there is a way to test whether Mersenne numbers are prime that is more efficient than general numbers.

It takes a lot of computation to prove that a large number is prime, but it is possible to produce a certificate of primality that can be quickly verified. One form of primality certificate is Pratt certificates and another kind is elliptic curve primality certificates.

Optimization

Some optimization problems, such as linear programming or more generally convex optimization, produce certificates that verify that a solution is optimal. Maybe the solution was found on a beefy computer but could be verified on a phone.

Lack of solution

It’s typically easier to prove a solution exists than to prove a solution does not exist. You can prove a solution exists by finding one. This may not be easy to do but easy to verify. Certifying that a problem as no solution is more difficult—how do you know whether you’ve looked hard enough?—but sometimes you can produce a certificate of infeasibility.

Footnotes

[1] The question of whether P = NP asks whether in some sense it is possible to efficiently compute solutions to a large class of problems whose solutions can be verified efficiently [4].

[2] The solution techniques can be justified, though not at the level of mathematics students have when taking an introductory differential equations course.

[3] In 1989 the largest known prime as 391581 × 2²¹⁶¹⁹³ − 1.

[4] Can a footnote have a footnote? Sure, why not. The P = NP problem asks whether a problem that can be verified in polynomial time can be solved in polynomial time. But if you didn’t already know this, you probably won’t find this description satisfying. It’s kinda subtle, and I won’t add a footnote to a footnote of a footnote.

The post Asymmetric generation / verification costs first appeared on John D. Cook.