I have some great news. For the first time, the total market cap as of 5/23/2017 for all cryptocurrencies is at \$80,000,000,000 (a month ago it was at \$30,000,000,000 but who knows what it will be in a month or two). Furthermore, as of 5/17/2017, for the first time cryptocurrencies other than Bitcoin consist of more than 50 percent of the total market cap for all cryptocurrencies. These historic events should not be taken lightly. I predict that in the future, cryptocurrencies will for the most part replace fiat currencies. The rise of cryptocurrencies will undoubtably change the world in many important ways. For example, some have predicted that cryptocurrencies will end all war (it will be hard to fund wars with cryptocurrencies)! To learn more about cryptocurrencies, you can read the original paper on the first cryptocurrency Bitcoin.
A proofofwork problem is a computational problem that one must do to in order to produce new coins in the cryptocurrency and to maintain the security of the cryptocurrency. For example, in Bitcoin, the proofofwork problem consists of finding suitable strings which produce exceptionally low SHA256 hashes (the hashes must be low enough so that only one person produces a such hash every 10 minutes or so). In this post, I am going to outline how employing many different kinds of more mathematical proofofwork problems will provide much better security for cryptocurrencies than if one were to employ only one type of proofofwork problem and how some of the issues that arise with useful proofofwork problems are resolvable.
I believe that hash problems are popular proofofwork problems for cryptocurrencies not because they are the best but simply because they are simple and these hashbased proof of work problems have been the best proof of work problems in instances where a proofofwork was needed before cryptocurrencies came into being. For example, hashbased proofofwork problems are used to thwart denialofservice attacks and spam since for a normal user the proofofwork problems are not too difficult to solve but the problems will be too difficult for an attacker to compute. While the hashbased proofofwork problems are ideal to thwarting denialofservice attacks and spammers, they are not ideal as proofofwork schemes for cryptocurrencies.
Cryptocurrencies with a many kinds of proofofwork problems can satisfy very lax requirements compared to cryptocurrencies with only one type of proofofwork problem.
The security of cryptocurrencies depends on the fact that no single entity can solve more than 50 percent of the proofofwork problems. If a malicious entity solves more than 50 percent of the proofofwork problems, then such an entity can undermine the security of the entire cryptocurrency (such an attack is called a 51 percent attack). If a cryptocurrency has only one kind of proofofwork problem, then that proofofwork problem must satisfy very strict requirements. But if the same cryptocurrency has many different kinds of proofofwork problems, then those proofofwork problems are only required to satisfy relatively mild conditions, and it is therefore feasible for many useful proofofwork problems to satisfy those conditions (here temporarily assume that there is a good protocol for removing broken proofofwork problems). Let me list those conditions right here.
The conditions colored orange are always absolutely essential for any proofofwork problem on a cryptocurrency. The conditions colored green are essential when there is only one kind of proofofwork problem, but these conditions in green are not necessary when there are many different kinds of proofofwork problems for the cryptocurrency.

Verifiable but intractible
These problems need to be difficult to solve but it must be easy to verify the solution to these problems.

Utility
The solution to the problem should have other uses than simply securing the cryptocurrency. The solution should have practical applications as well, or at the very least, the solutions to the problem should advance mathematics or science. Right now, the proofofwork problem for Bitcoin is amounts to simply finding data whose SHA256 hash is exceptionally low.

Scalability.
For Bitcoin, the proofofwork problems need to be solved approximately every 10 minutes (with an exponential distribution), and in any cryptocurrency, the proofofwork problem must consistently be solved in about the same amount of time. As time goes on, the proofofwork problems need to get more difficult to accomodate for faster computers, quicker algorithms, more people working on the problem, and more specialized computer chips solving the problem. If $X$ is the distribution of the amount of time it takes to compute the proofofwork problem, then $X$ should have a consistent mean and the distributions $X,1/X$ should have low variance (we do not want to solve the problem for one block in one second and solve the problem for the next block in one hour).

Efficient automatic generation
The proofofwork problems need to be generated automatically based on the previous blocks in the blockchain. Cryptocurrencies are decentralized so there cannot be a central agency which assigns each individual proofofwork problem.

Progressfreeness
Progress freeness for search problems means that the probability that the first solution is found at time $t$ follows an exponential distribution. Progress freeness for problems whose objective is to optimize $f(x)$ means that for all $\alpha$ the probability of finding a solution where $f(x)\geq\alpha$ at time $t$ follows an exponential distribution. In other words, solutions are found randomly without regard of how long one has been working on obtaining a solution. Said differently, if Alice spends 30 minutes attempting to find a solution without finding a solution, then Alice will not have any advantage if she has not spent any of the 30 minutes searching for a solution. If there is only one kind of proofofwork problem for a cryptocurrency, and that proofofwork problem is far from progress free, then the entity who has the fastest computer will always win, and such an entity could launch a 51 percent attack. As an extreme example of why progressfreeness is needed, suppose that a problem always takes 1000 steps to solve. If Alice has a computer that can do 500 steps a second and Bob has a computer that can do 1000 steps a second, then Bob will solve the problem in 1 second and Alice will solve the problem in 2 seconds. Therefore Bob will always win. However, a lack of progress freeness is no longer a problem if in the cryptocurrency, there are many proofofwork problems running simultaneously. For example, in the above scenario, even if Bob is able to solve a particular problem better than everyone else, Bob will have to spend much of his computational power solving that particular problem, and Bob will not have enough resources to solve the other proofofwork problems, and therefore Bob will be unable to launch a 51 percent attack.

Optimizationfreeness
By optimizationfreeness, I mean that people need to be confident that in the future an entity will not be able to obtain a faster algorithm than we have today. The motivation behind optimization freeness is that if an entity has a secret algorithm which is much faster or better than all the other algorithms, then such an entity will be able to launch a 51 percent attack. However, a cryptocurrency employs many different kinds of proofofwork problems, then such an entity will be able to solve a particular problem better than all others but that entity will not be able to launch a 51 percent attack. In fact, if a cryptocurrency employs many different kinds of proofofwork problems, then optimization freeness will make the cryptocurrency less secure instead of more secure.

Precomputation resistance
Precomputation refers to when an entity solves a proofofwork problem before the proofofwork problem for a particular block is determined.

Unlimited problems
There needs to be an unlimited supply of proofofwork problems to solve. This is only an issue if there is only one kind of proofofwork problem for the cryptocurrency. If there are many kinds of proofofwork problems in a cryptocurrency, then a particular type of proofofwork problem can simply be removed by an automatic procedure or when all of the particular instances of the problem have been solved.
The problemremovalprotocol
So for a cryptocurrency which employs many different kinds of proofofwork problems, the list of all problems which are currently being used in the cryptocurrency shall be called the problem schedule. If there are many different types of proofofwork problems in the problem schedule, there is a good chance that a few of these proofofwork problems should eventually be broken and should therefore be removed from the problem schedule. Since cryptocurrencies are meant to be as decentralized as possible, the process of removing broken proofofwork problems from he problem schedule needs to be done automatically without a change to the programming of the cryptocurrency. Let me therefore list three different ways that a proofofwork problem could be automatically removed from the problem schedule.

Formal proof of break
The proofofwork problem will be considered to be broken and removed from the problem schedule if an entity submits a formal proof that the proofofwork problem can be solved in polynomial time. The entity who submits the formal proof will win a predetermined number of blocks in the blockchain and hence new coins.

Heuristic algorithm for break
The proofofwork problem will be considered to be broken and removed form the problem schedule if an entity named Alice submits an algorithm that breaks the proofofwork problem. For search problems, the algorithm is simply expected to consistently find a fast and accurate solution even if the difficulty of the proofofwork problem is increased to very high levels. For optimization problems, the breaking algorithm must quickly and consistently give solutions which are at least as good as solutions obtained using other algorithms. In the case of optimization problems broken by a heuristic algorithm, the protocol for removing a problem from the problem schedule is more involved. Alice will first need to openly submit her algorithm for solving the proofofwork problem. Alice is then required to follow her own algorithm and obtain a solution which is at least as optimized as the solutions produced by all other entities (keep in mind that other entities may use Alice’s algorithm or attempt to improve upon Alice’s algorithm. Furthermore, the optimization process will last long enough for other entities to attempt to improve upon Alice’s algorithm). If Alice satisfies these requirements, then the problem is removed from the problem schedule, Alice is given a predetermined number of blocks in the blockchain, and Alice will be awarded plenty of coins.

Automatic removal of broken proofofwork problems
For search problems, if the proofofwork problem is repeatedly quickly solved (possibly with multiple solutions) even when the difficulty of the problem increases without bounds, then the proofofwork problem will be automatically removed from the problem schedule. For optimization problems, if the best solution or best solutions are consistently obtained early within the timespan for solving the problem, then the proofofwork problem will automatically be removed from the problem schedule and after the problem is removed, no entity will be awarded any blocks in the blockchain as a prize.
The automatic removal system should preferrably be implemented in a way so that an entity with a secret algorithm can always provide the best solutions to this proofofwork problem simply by producing solutions which always win but which fall below the thresholdofremoval. However, the automatic removal system should also be implemented so that if the secret algorithm that breaks the system becomes publicly available, then the problem will easily be removed. In other words, an entity can cross the thresholdofremoval if he wants to but such an entity can just as easily remain just below the thresholdofremoval in order to obtain many coins.
The benefits of having many kinds of proofofwork problems
The most obvious benefit to our composite proofofwork system with many kinds of proofofwork problems is that our proofofwork system allows for a wide flexibility of problems and hence it allows for proofofwork problems which have useful benefits besides securing the cryptocurrency.
Useful proofofwork problems will obviously provide benefits since the solution to those proofofwork problems will have practical applications or at least advance mathematics. Useful proofofwork problems will also provide a benefit to the cryptocurrencies themselves since useful proofofwork problems will greatly help the public image of cryptocurrencies.
The public image of cryptocurrencies is one of the most important battles that advocates of cryptocurrencies must face. After all, cryptocurrencies directly threaten many of the powers that governments possess, and governments have the power to ban cryptocurrencies. Not only can governments ban cryptocurrencies, but powerful governments also have the power to undermine the security of cryptocurrencies by launching 51 percent attacks against them since governments have nearly unlimited resources. Cryptocurrencies therefore need to obtain and maintain a strong public image in order to avoid governmental backlash as much as possible.
Another reason for cryptocurrencies need to obtain a strong public image is that cryptocurrencies are still new and many people do not consider cryptocurrencies as legitimate currencies (those dinosaurs are wrong). People therefore need to accept cryptocurrencies as legitimate currency.
Today, many people view the process of mining cryptocurrencies and maintaining the blockchain for a cryptocurrency as being incredibly wasteful and bad for the environment, and these criticisms against cryptocurrencies are justified. Cryptocurrency advocates would respond by saying that cryptocurrency mining is useful for securing and decentralizing the blockchain and hence not wasteful, but in any case, it is much better and much more efficient for these proofofwork problems to have applications besides securing the blockchain (many cryptocurrencies have attempted to do away with proofofwork problems since proofofwork problems are seen as wasteful). I personally will not give cryptocurrencies my full endorsement until they are used to solve useful problems with mathematical, scientific, or practical merit.
Today people receive about 4 million dollars worth of bitcoins every day from mining these bitcoins. Unfortunately, in order to mine these bitcoins, people need to use much energy to power the computers that make these calculations. Imagine how much cryptocurrencies can be used to advance mathematics and science if the proofofwork problems are selected with scientific advancements in mind. Imagine how much these advancements to science could boost the public image of cryptocurrencies.
It is less obvious that our composite proofofwork system also strengthens the security of the cryptocurrency against 51 percent attacks. It is much more straightforward for an entity to launch a 51 percent attack against a cryptocurrency with only one type of proofofwork problem than it is to launch an attack against a cryptocurrency with many types of proofofwork problems. After all, to launch a 51 percent attack against a single proofofwork hashbased problem, one must simply spend a lot of money to produce a lot of ASICs for solving that problem and at any time the attacker can completely break the problem. On the other hand, to launch a 51 percent attack against many proofofwork problems, one must obtain many different types of ASICs in order to solve many different kinds of problems. Furthermore, in some cases, an attacker may not be able to solve some of these problems since the attacker may not have access to a secret algorithm for solving this problem, and an attacker will not have access to some specialized knowledge which will allow one to quickly solve the problem.
How our system could be implemented on established cryptocurrencies
Cryptocurrencies are supposed to be decentralized currencies. Since cryptocurrencies are supposed to be decentralized, there should be as few changes to cryptocurrencies as possible. This poses a problem for cryptocurrencies which are attempting to switch from useless proofofwork problems to useful proofofwork problems. My solution is to only make a change to the cryptocurrency protocol once. In order to minimize backlash and other chaos, the changes stated in the cryptocurrency protocol will be implemented gradually. Let me now give an example of how the change from useless proofofwork problems to useful proofofwork problems could take place. Let $t$ be the number of years before the change of the proofofwork protocol were to take place. When $t=4$, the cryptocurrency will begin selecting 144 different proofofwork problems to be used in the cryptocurrency. At time $t=1$, all 144 of the proofofwork problems will be selected and the changes to the cryptocurrency protocol will be finalized. At time $t=0$, the cryptocurrency protocol will be modified but these modifications will take effect over a process of 6 years. Every day an average of 144 blocks will be generated. Every month from time $t=0$ to time $t=6$, two out of these 144 proofofwork problems will be selected at random to be implemented into the problem schedule. At the $m$th month from $t=0$, every day approximately $1442m$ of the blocks on the blockchain will have a hashbased proofofwork problem while the $2m$ other blocks will be from the 144 proofofwork problems which have already been implemented into the problem schedule. At time $t=10$, a collection of new proofofwork problems will be selected to replace the problems which have already been broken or which will be broken in the future.