This is pretty much the P vs NP problem. Finding an input that makes some program return true is, most likely, exponentially harder than checking that the program returns true on some given input. The exponent is the running time of the program. To take a strawman example, if you have a recognizer that takes 10 seconds to tell you if an input is suitable, you might be able to generate a suitable input in an hour. Then you add some complexity to the recognizer so it takes 11 seconds instead of 10, and find that the generator now takes 2 hours. Adding another second to the recognizer will lead to 4 hours in the generator, and so on. The work required from the generator grows as an exponential of the work done by the recognizer, unless the recognizer is of a special kind which allows fast generators.
It’s especially noticeable when you try to write fiction, compose music or make a video game because you feel like you’re so good at appreciating them. You quickly realize that, even though your recognizer works well, using a trial-and-error generator is futile. The only solution is to hope that your recognizer is of a special kind, and you can build a fast generator for it. That’s known as creativity. And then it leads to changes in your recognizer, a.k.a. your taste improves, and you start all over again.
This is pretty much the P vs NP problem. Finding an input that makes some program return true is, most likely, exponentially harder than checking that the program returns true on some given input. The exponent is the running time of the program. To take a strawman example, if you have a recognizer that takes 10 seconds to tell you if an input is suitable, you might be able to generate a suitable input in an hour. Then you add some complexity to the recognizer so it takes 11 seconds instead of 10, and find that the generator now takes 2 hours. Adding another second to the recognizer will lead to 4 hours in the generator, and so on. The work required from the generator grows as an exponential of the work done by the recognizer, unless the recognizer is of a special kind which allows fast generators.
It’s especially noticeable when you try to write fiction, compose music or make a video game because you feel like you’re so good at appreciating them. You quickly realize that, even though your recognizer works well, using a trial-and-error generator is futile. The only solution is to hope that your recognizer is of a special kind, and you can build a fast generator for it. That’s known as creativity. And then it leads to changes in your recognizer, a.k.a. your taste improves, and you start all over again.
Oh, right, yup. The P vs NP analog is a very good parallel.