The existence of problems whose answers are hard to verify does not entail that this verification is harder than finding the answer itself.
That’s not quite the relevant question. The point of hiring an expert is that it’s easier to outsource the answer-finding to the expert than to do it oneself; the relevant question is whether there are problems for which verification is not any easier than finding the answer. That’s what I mean by “hard to verify”—questions for which we can’t verify the answer any faster than we can find the answer.
I thought some more about the IP analogy yesterday. In many cases, the analogy just doesn’t work—verifying claims about the real world (i.e. “I’ve never heard of a milkmaid who had cowpox later getting smallpox”) or about human aesthetic tastes (i.e. “this car is ugly”) is fundamentally different from verifying a computation; we can verify a computation without needing to go look at anything in the physical world. It does seem like there are probably use-cases for which the analogy works well enough to plausibly adopt IP-reduction algorithms to real-world expert-verification, but I do not currently have a clear example of such a use-case.
Okay, so we agree that it’s improbable (at least for decision problems) to be able to verify an answer faster than finding it. What you care about are cases where verification is easier, as is conjectured for example for NP (where verification is polynomial, but finding an answer is supposed to not be).
For IP, if we only want to verify any real-world property, I actually have a simple example I give into my intro to complexity theory lectures. Imagine that you are color-blind (precisely, a specific red and a specific green look exactly the same to you). If I have two balls, perfectly similar except one is green and the other is red, I can convince you that these balls are of different colors. It is basically the interactive protocol for graph non-isomorphism: you flip a coin, and depending on the result, you exchange the balls without me seeing it. If I can tell whether you exchanged the balls a sufficient number of times, then you should get convinced that I can actually differentiate them.
Of course this is not necessarily applicable to questions like tastes. Moreover, it is a protocol for showing that I can distinguish between the balls; it does not show why.
It does still require some manipulation ability—we have to be able to experimentally intervene (at reasonable expense). That doesn’t open up all possibilities, but it’s at least a very large space. I’ll have to chew on it some more.
It can be very easy to come up with answers. The hard part is often verifying.
Example 1: Fermats Last Therom. One man spent a short time to state the answer, hundreds spent decades to verify it.
Example 2: Solve for x:
Problem: floor(37/4.657 + 3^9) = x.
Proposed solution (this took me 4 seconds to write down) X = 1,456,299
It will probably take you longer than 4 seconds to verify or disprove my solution.
That’s not quite the relevant question. The point of hiring an expert is that it’s easier to outsource the answer-finding to the expert than to do it oneself; the relevant question is whether there are problems for which verification is not any easier than finding the answer. That’s what I mean by “hard to verify”—questions for which we can’t verify the answer any faster than we can find the answer.
I thought some more about the IP analogy yesterday. In many cases, the analogy just doesn’t work—verifying claims about the real world (i.e. “I’ve never heard of a milkmaid who had cowpox later getting smallpox”) or about human aesthetic tastes (i.e. “this car is ugly”) is fundamentally different from verifying a computation; we can verify a computation without needing to go look at anything in the physical world. It does seem like there are probably use-cases for which the analogy works well enough to plausibly adopt IP-reduction algorithms to real-world expert-verification, but I do not currently have a clear example of such a use-case.
Okay, so we agree that it’s improbable (at least for decision problems) to be able to verify an answer faster than finding it. What you care about are cases where verification is easier, as is conjectured for example for NP (where verification is polynomial, but finding an answer is supposed to not be).
For IP, if we only want to verify any real-world property, I actually have a simple example I give into my intro to complexity theory lectures. Imagine that you are color-blind (precisely, a specific red and a specific green look exactly the same to you). If I have two balls, perfectly similar except one is green and the other is red, I can convince you that these balls are of different colors. It is basically the interactive protocol for graph non-isomorphism: you flip a coin, and depending on the result, you exchange the balls without me seeing it. If I can tell whether you exchanged the balls a sufficient number of times, then you should get convinced that I can actually differentiate them.
Of course this is not necessarily applicable to questions like tastes. Moreover, it is a protocol for showing that I can distinguish between the balls; it does not show why.
That is an awesome example, thank you!
It does still require some manipulation ability—we have to be able to experimentally intervene (at reasonable expense). That doesn’t open up all possibilities, but it’s at least a very large space. I’ll have to chew on it some more.
It can be very easy to come up with answers. The hard part is often verifying. Example 1: Fermats Last Therom. One man spent a short time to state the answer, hundreds spent decades to verify it. Example 2: Solve for x: Problem: floor(37/4.657 + 3^9) = x. Proposed solution (this took me 4 seconds to write down) X = 1,456,299 It will probably take you longer than 4 seconds to verify or disprove my solution.