This is interesting, because at least in theoretical computer science, verifying something is conjectured to be easier that creating it: the P vs NP question for example, where almost all complexity theorist conjectures that P is not equal to NP. That is to say, some problems in NP (problems for which we can verify a solution in polynomial time) are conjectured to not be in P (problems for which we can find a solution in polynomial time).
On the other hand, your examples hint at cases where verifying something (the quality of the product for example) is almost as hard as creating this thing (building a quality product).
Not sure if this adds anything to the conversation, but I found the connection surprising.
In CS, there are some problems whose answer is easier to verify than to create. The same is certainly true in the world in general—there are many objectives whose completion we can easily verify, and those are well-suited to outsourcing. But even in CS, there are also (believed to be) problems whose answer is hard to verify.
But the answer being hard to verify is different from a proof being hard to verify—perhaps the right analogy is not NP, but IP or some variant thereof.
This line of reasoning does suggest some interesting real-world strategies—in particular, we know that MIP = NEXPTIME, so quizzing multiple alleged experts in parallel (without allowing them to coordinate answers) could be useful. Although that’s still not quite analogous, since IP and MIP aren’t about distinguishing real from fake experts—just true from false claims.
The existence of problems whose answers are hard to verify does not entail that this verification is harder than finding the answer itself. Do you have examples of the latter case? Intuitively, it seems akin to comparing any (deterministic) complexity class with its non-deterministic version, and any problem solvable in the former is verifiable in the latter, by dropping the proof and just solving the problem.
For the difference between verifying a proof and an answer, I agree that interactive protocols are more appropriate for the discussion we’re having. Even if interactive protocols are not about distinguishing between different experts, they might serve this point indirectly by verifying the beauty of a car design or the security of a system. That is, we could (in theory) use interactive proofs to get convinced with good probability of the quality of a candidate-expert’s output.
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.
This is interesting, because at least in theoretical computer science, verifying something is conjectured to be easier that creating it: the P vs NP question for example, where almost all complexity theorist conjectures that P is not equal to NP. That is to say, some problems in NP (problems for which we can verify a solution in polynomial time) are conjectured to not be in P (problems for which we can find a solution in polynomial time).
On the other hand, your examples hint at cases where verifying something (the quality of the product for example) is almost as hard as creating this thing (building a quality product).
Not sure if this adds anything to the conversation, but I found the connection surprising.
In CS, there are some problems whose answer is easier to verify than to create. The same is certainly true in the world in general—there are many objectives whose completion we can easily verify, and those are well-suited to outsourcing. But even in CS, there are also (believed to be) problems whose answer is hard to verify.
But the answer being hard to verify is different from a proof being hard to verify—perhaps the right analogy is not NP, but IP or some variant thereof.
This line of reasoning does suggest some interesting real-world strategies—in particular, we know that MIP = NEXPTIME, so quizzing multiple alleged experts in parallel (without allowing them to coordinate answers) could be useful. Although that’s still not quite analogous, since IP and MIP aren’t about distinguishing real from fake experts—just true from false claims.
The existence of problems whose answers are hard to verify does not entail that this verification is harder than finding the answer itself. Do you have examples of the latter case? Intuitively, it seems akin to comparing any (deterministic) complexity class with its non-deterministic version, and any problem solvable in the former is verifiable in the latter, by dropping the proof and just solving the problem.
For the difference between verifying a proof and an answer, I agree that interactive protocols are more appropriate for the discussion we’re having. Even if interactive protocols are not about distinguishing between different experts, they might serve this point indirectly by verifying the beauty of a car design or the security of a system. That is, we could (in theory) use interactive proofs to get convinced with good probability of the quality of a candidate-expert’s output.
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.