Coming Up With Good Stuff in Polynomial Time
(Since I had not posted anything in a long time now, here is something I wrote for The Scholars’ Avenue long ago.)
Even though coming up with good stuff has lots of applications in areas such as living life, having fun, impressing girls and designing fault tolerant systems for distributed applications, it has not been studied completely and there does not exist any known algorithm to solve it efficiently. Human beings still rely on those random sparks of creativity they experience when on crack or when having a bath in Syracuse. The earliest known example of such an incidence is when the famous homo erectus Jon (71st descendant of Adam) came up with the idea of controlled fire. Although the exact nature of motivation has not been documented, a popular folklore that has been passed from generation to generation by word of mouth does suggest that he had dedicated his invention to his neighbour’s daughter.
Ever since Jon, several attempts have been made by human beings to come up with good stuff. Examples include things such as knife, flute, sewing needles, boomerang, alcohol, dental drill, agriculture, ice skate, comb, noodles, horseshoe, chess, toilet paper, hand glider, coffee and hydrostatic balance. More recently, Led Zeppelin’s Stairway to Heaven, Alonzo Church’s Lambda Calculus and Douglas Adams’ Hitchhikers’ Guide to the Galaxy have been widely regarded as good stuff. However, as was pointed out earlier, the process has been fairly random. In fact, most of the people who did manage to come up with good stuff complained that it was almost impossible to do that when they wanted to. We, however, propose an algorithm that will give humans more control over the whole process.
We will exploit the fact that even though coming up with good stuff is difficult, deciding whether a given stuff is good or not is fairly easy and so, can be trivially done in polynomial time. For example, even though composing an award winning song is difficult, deciding whether a song might win awards or not is fairly easy. Taking into account the above observation, a simplistic algorithm can be designed straightaway. First of all, invoke your random stuff generator and next, check whether the stuff generated is good or not by invoking your goodness verifier. Since both these steps are trivial, they can be carried out in polynomial time. If the generated stuff is good, then you are done, else repeat the whole process. Obviously, there is something wrong, since the algorithm seems to be too trivial to have any actual use. The catch is that although each step is quick, the number of times you may have to repeat it may be very large in the worst case. Moreover, when you discard a particular random stuff because it was not good and generate a new one randomly, you might end up having something even worse.
An improvement over the simplistic algorithm can be achieved by using a subroutine that calculates the goodness slope. The goodness slope of a given stuff is basically a direction in which it should be modified in order to increase its goodness. So if we can calculate the goodness slope each time we generate a stuff, we can make sure that each iteration improves the goodness of the stuff. Building the goodness slope calculator is, however, a little tricky and can only be done through some amount of practice. It is not too difficult though, because the algorithm does not require the subroutine to return the best possible direction. All it requires is one direction in which there is some improvement. However, the subroutine might still fail to do this with consistency, i.e. without failure. So, the idea is to use a combination of both the random stuff generator and the goodness slope calculator. You basically start by generating a random stuff. If it is good, then you are done, else you invoke the slope calculator on it. If the slope calculator is able to give you a slope, you modify your stuff accordingly, else, you generate a new random stuff. The exact algorithm is as follows.
Step 1. Generate a random stuff.
Step 2. Check whether the stuff is good or not. If yes, then return the stuff and exit, else move to the next step.
Step 3. Invoke the goodness slope calculator on the stuff.
Step 4. If the goodness slope calculator is able to return a slope, move in that direction, modify the stuff accordingly and goto step 2, else, goto step 1.
As we can see, the above algorithm still requires lots of repetitions of steps and if your goodness slope calculator is completely useless, it is exactly equivalent to the previous simplistic algorithm. However, it can be shown that on an average, the goodness slope calculator can be made efficient enough to make the above algorithm polynomial. The details are left to the reader as an exercise.
We implemented the algorithm on some human subjects in order to verify its correctness and the results were outstanding. The subjects were monitored for about a week and it was noted that they all came up with at least three good stuffs per day. Besides, there was also a noticeable (more than 112%) improvement in the quality of their love lives at the end of the week. However, the amount of amazingly good stuff they came up with was still fairly low. In fact, the problem of coming up with amazingly good stuff is still open and the interested reader may take it up as a research exercise.
