Verification Is Not Easier Than Generation In General

I think most people's intuitions come from more everyday experiences like:

• It's easier to review papers than to write them.
• Fraud is often caught using a tiny fraction of the effort required to perpetrate it.
• I can tell that a piece of software is useful for me more easily than I can write it.

These observations seem relevant to questions like "can we delegate work to AI" because they are ubiquitous in everyday situations where we want to delegate work.

The claim in this post seems to be: sometimes it's easier to create an object with property P than to decide whether a borderline instance satisfies property P. You chose a complicated example but you just as well have used something very mundane like "Make a pile of sand more than 6 inches tall." I can do the task by making a 12 inch pile of sand, but if someone gives me a pile of sand that is 6.0000001 inches I'm going to need very precise measurement devices and philosophical clarification about what "tall"means.

I don't think this observation undermines the claim that "it is easier to verify that someone has made a tall pile of sand than to do it yourself." If someone gives me a 6.000001 inch tall pile of sand I can say "could you make it taller?" And if I can ask for a program that halts and someone gives me a program that looks for a proof of false in PA, I can just say "try again."

I do think there are plenty of examples where verification is not easier than generation (and certainly where verification is non-trivial). It's less clear what the relevance of that is.

$P\ne NP$ deserves a little more credit than you give it. To interpret the claim correctly, we need to notice $P$ and $NP$ are classes of decision problems, not classes of proof systems for decision problems. You demonstrate that for a fixed proof system it is possible that generating proofs is easier than verifying proofs. However, if we fix a decision problem and allow any valid (i.e. sound and complete) proof system, then verifying cannot be harder than generating. Indeed, let $S_1$ be some proof system and $A$ an algorithm for generating proofs (i.e. an algorithm that finds a proof if a proof exists and outputs "nope" otherwise). Then, we can construct another proof system $S_2$, in which a "proof" is just the empty string and "verifying" a proof for problem instance $x$ consists of running $A\left(x\right)$ and outputting "yes" if it found an $S_1$-proof and "no" otherwise. Hence, verification in $S_2$ is no harder than generation in $S_1$. Now, so far it's just $P\subseteq NP$, which is trivial. The non-trivial part is: there exist problems for which verification is tractable (in some proof system) while generation is intractable (in any proof system). Arguably there are even many such problems (an informal claim).

I'm afraid that this take is incredibly confused, so much that it's hard to know where to start with correcting it.

Maybe the most consequential error is the misunderstanding of what "verify" means in this context. It means "checking a proof of a solution" (which in the case of a decision problem in NP would be a proof of a "yes" answer). In a non-mathematical context, you can loosely think of "proof" as consisting of reasoning, citations, etc.

That's what went wrong with the halting problem example. The generator did not support their claim that the program halts. If they respond to this complaint by giving us a proof that's too hard, we can (somewhat tautologically) ensure that our verifier job is easy by sending back any program+proof pair where the proof was too hard to verify.

The most trivial programs that halt are also trivially verifiable as halting, though.  Yes, you can't have a fully general verification algorithm, but e.g. "does the program contain zero loops or recursive calls" covers the most trivial programs (for my definition of "trivial", anyway).  I think this example of yours fails to capture the essence—which I think is supposed to be "someone easily spewing out lots of incomprehensible solutions to a problem".

In fact, more generally, if there is a trivial algorithm to generate solutions, then this immediately maps to an algorithm for verifying trivial solutions: run the trivial algorithm for a reasonable number of steps (a number such that the generation would no longer be called "trivial" if it took that long) and see if the proposed solution appears among them.  The hardest part is knowing what that algorithm was—but by assumption the algorithm was trivial, which puts some limits on how hard finding it can be.^[1]

The main path that might still qualify as "trivially generating lots of solutions that are hard to verify by someone who has some notion of how the generation works" is if the generation process includes randomness.  E.g. make a comprehensible program, then insert a bunch of trash and permute things around.  Or, say, have a number maze and the question is "Is there a path through these numbers such that sha256(those numbers) = 0xabcde?"—and the person who made the maze did so by picking random numbers, computing their sha256, putting them into a maze, and filling the rest of the maze with more random numbers.  I probably would have recommended that example.^[2]

This brings it back to NP, incidentally: if the generation process was trivial, then it must have taken a "reasonable" amount of time; and if it used N bits of randomness, then a verifier has 2^N possibilities to try, and if it guesses right the first time (a nondeterministic machine) then it terminates quickly.  But this time the verification process is NP, while the generation process is P.

1. ^{^}

   Though if we concern ourselves with not "trivial" algorithms but rather "algorithms that aren't too complicated"—which might be approximated by "algorithms specified in under N characters"—then there are exponentially many algorithms to sort through.

2. ^{^}

   Or, a version that meets more rigorous constraints: The predicate is, "Is this an n x k grid of bytes such that there is a nonrepeating path through the grid, such that sha256(those bytes), xored with the top row of bytes, yields zero?"  The generation algorithm is to pick random bytes, sha256 them, draw a random path in a grid and put them there, fill out the rest of the grid with random bytes, and put the sha256 result as the top row of bytes.

It's not clear to me what the slogan is intended to mean, and the example only confuses me further. In the first paragraph of the OP, "generate" appears to mean "find a solution to a given problem". In the supposed counterexample, it means "find a problem that has a given solution". These are very different things. The former task is hard for problems in NP–P, the latter task is typically trivial.

E.g. "does this plan avoid having a steganographically encoded world-ending message hidden in it" is more co-NPish than NP-ish. Like, just showing me the plan doesn't make it easy to verify that there isn't a hidden message, even if there isn't a hidden message. Checking whether a sequence of actions is the first half of a strategy to take over the world is potentially more like P-space. 

I think there's a fundamental asymmetry in the case you mentioned--it's not verifying whether a program halts that's difficult, it's writing an algorithm that can verify whether any program halts. In other words, the problem is adversarial inputs. To keep the symmetry, we'd need to say that the generation problem is "generate all computer programs that halt," which is also not possible.

I think a better example would be, how hard is it to generate a semiprime? Not hard at all: just generate 2 primes and multiply them. How hard is it to verify a number is semiprime? Very hard, you'd have to factor it.

I think this is kinda like the no free lunch theorem - it sounds kinda profound but relies on using the set of all problems/data distributions, which is very OOD from any problem that originates in physical reality.

What examples of practical engineering problems actually have a solution that is harder to verify than to generate? 

And I thought uncomputability is only true for programs that don't halt? A blank program can definitely be verified to halt.

I am exactly in this post's target audience. Epic post.

First, I want to summarize what I understand to be what your example is an example of:
"A triple consisting of
1) A predicate P
2) the task of generating any single input x for which P(x) is true
3) the task of, given any x (and given only x, not given any extra witness information), evaluating whether P(x) is true
"

For such triples, it is clear, as your example shows, that the second task (the 3rd entry) can be much harder than the first task (the 2nd entry).

_______

On the other hand, if instead one had the task of producing an exhaustive list of all x such that P(x), this, I think, cannot be easier that verifying whether such a list is correct (provided that one can easily evaluate whether x=y for whatever type x and y come from), as one can simply generate the list, and check if it is the same list.

Another question that comes to mind is: Are there predicates P such that the task of verifying instances which can be generated easily, is much harder than the task of verifying those kinds of instances?

It seems that the answer to this is also "yes": Consider P to be "is this the result of applying this cryptographic hash function to (e.g.) a prime number?". It is fairly easy to generate large prime numbers, and then apply the hash function to it. It is quite difficult to determine whether something is the hash of a prime number (... maybe assume that the hash function produces more bits for longer inputs in order to avoid having pigeonhole principle stuff that might result in it being highly likely that all of the possible outputs are the hash of some prime number. Or just put a bound on how big the prime numbers can be in order for P to be true of the hash.)

(Also, the task of "does this machine halt", given a particular verifying process that only gets the specification of the machine and not e.g. a log of it running, should probably(?) be reasonably easy to produce machines that halt but which that particular verifying process will not confirm that quickly.
So, for any easy-way-to-verify there is an easy-way-to-generate which produces ones that the easy-way-to-verify cannot verify, so that seems to be another reason why "yes", though, there may be some subtleties here?)

TypeError: Comparing different "solutions".

How do I know that I generated a program that halts?

a) I can prove to myself that my program halts => the solution consists of both the program and the proof => the verification problem is a sub-problem of the generation problem.

b) I followed a trusted process that is guaranteed to produce valid solutions => the solution consists of both the program and the history that generated the proof of the process => if the history is not shared between the 2 problems, then you redefined "verification problem" to include generation of all of the necessary history, and that seems to me like a particularly useless point of view (for the discussion of P vs NP, not useless in general).

In the latter point of view, you could say:

Predicate: given a set of numbers, is the first the sum of the latter 2?

Generation problem: provide an example true solution: "30 and prime factors of 221"

Verification problem: verify that 30 is the sum of prime factors of 221

WTF does that have to say about P vs NP? ¯\_(ツ)_/¯

Predicate: given a program, does it halt?

Generation problem: generate a program which halts.

Verification problem: given a program, verify that it halts.

In this example, I'm not sure that generation is easier than verification in the most relevant sense. 

In AI alignment, we have to verify that some instance of a class satisfies some predicate. E.g. is this neural network aligned, is this plan safe, etc. But we don't have to come up with an algorithm that verifies if an arbitrary example satisfies some predicate. 

The above example is only relevant if there is some program P that halts, where it's easier to generate P than to verify that P halts. If that's the case, then it there might be some dangerous output O, where it's easier for the AI to generate O than it is for us to verify O.

Generally, statement "solutions of complex problems are easy to verify" is false. Your problem can be EXPTIME-complete, but not in NP, especially if NP=P, because EXPTIME-complete problems are strictly not in P.

And even if some problem is NP-problem, we often don't know verification algorithm.

Would it be correct to consider things like proof by contradiction and proof by refutation as falling on the generation side, as they both rely on successfully generating a counterexample?

Completely separately, I want to make an analogy to notation in the form of the pi vs tau debate. Short background for those who don't want to wade through the link (though I recommend it, it is good fun): pi, the circle constant, is defined as the ratio between the diameter of a circle and its circumference; tau is defined as the ratio between the radius of a circle and its circumference. Since the diameter is twice the radius, tau is literally just 2pi, but our relentless habit of pulling out or reducing away that 2 in equations makes everything a little harder and less clear than it should be.

The bit which relates to this post is that it turns out that pi is the number of measurement. If we were to encounter a circle in the wild, we could characterize the circle with a length of string by measuring the circle around (the circumference) and at its widest point (the diameter). We cannot measure the radius directly. By contrast, tau is the number of construction: if we were to draw a circle in the wild, the simplest way is to take two sticks secured together at an angle (giving the radius between the two points), hold one point stationary and sweep the other around it one full turn (the circumference).

Measurement is a physical verification process, so I analogize pi to verification. Construction is the physical generation process, so I analogize tau to generation.

I'm on the tau side in the debate, because cost of adjustment is small and the clarity gains are large. This seems to imply that tau, as notation, captures the circle more completely than pi does. My current feeling, based on a wildly unjustified intuitive leap, is that this implies generation would be the more powerful method, and therefore it would be "easier" to solve problems within its scope.

(Not sure if I'm missing something, but my initial reaction:)

There's a big difference between being able to verify for some specific programs if they have a property, and being able to check it for all programs.

For an arbitrary TM, we cannot check whether it outputs a correct solution to a specific NP complete problem. We cannot even check that it halts! (Rice's theorem etc.)

Not sure what alignment relevant claim you wanted to make, but I doubt this is a valid argument for it.