I used to believe that one day all human labour would be automated. Upon further reflection, I realize that I am wrong. The question of whether or not machines will someday replace all humans depends crucially on whether or not P is equal to NP. Jobs that will eventually be automated will be the ones that can be solved easily with an algorithm. In computer science parlance, these are problems in the computational complexity class P (solvable in polynomial time). For example, traditional travel agents have disappeared faster than bluefin tuna because their task is pretty simple to automate. However, not all travel agents will disappear. The ones that survive will be more like concierges that put together complex travel arrangements or require negotiating with many parties.

Eventually, the jobs that humans will hold (barring a collapse of civilization as we know it) will involve solving problems in the complexity class NP (or harder). That is not to say that machines won’t be doing some of these jobs, only that the advantage of machines over humans will not be as clear cut. While it is true that if we could fully reproduce a human and make it faster and bigger then it could do everything that a human could do better but as I blogged about before, I think it will be difficult to exactly reproduce humans. Additionally, for some very hard problems that don’t even have any good approximation schemes, blind luck will play an important role in coming up with solutions. Balancing different human centric priorities will also be important and that may be best left for humans to do. Even if it turns out that P=NP there could still be some jobs that humans can do like working on undecidable problems.

So what are some jobs that will be around in the NP economy? Well, I think mathematicians will still be employed. Theorems can be verified in polynomial time but there are no known algorithms in P to generate them. That is not to say that there won’t be robot mathematicians and mathematicians will certainly use automated theorem proving programs to help them (e.g. see here). However, I think the human touch will always have some use. Artists and comedians will also have jobs in the future. These are professions that require intimate knowledge of what it is like to be human . Again, there will be machine comics and artists but they won’t fully replace humans. I also think that craftsmen like carpenters, stone masons, basket weavers and so forth could also make a comeback. They will have to exhibit some exceptional artistry to survive but the demand for them could increase since some people will always long for the human touch in their furniture and houses.

The question then is whether or not there will be enough NP jobs to go around and whether or not everyone is able and willing to hold one. To some, an NP economy will be almost Utopian – everyone will have interesting jobs. However, there may be some people who simply don’t want or can’t do an NP job. What will happen to them? I think that will be a big (probably undecidable) problem that will face society in the not too distant future, provided we make it that far.