Some students argue that the exercise “find the largest value” is too hard. This raises the question “What do we mean by hard problem”? Some problems are hard to understand, some are hard to translate into a program and some are really hard to solve, even if you have a super-computer.
I would argue that “find the largest value” is not a hard problem, because:
- Most people can find the largest value (biggest apple, more valuable money) easily in real life.
- People have been doing this since pre-historic times
- Even a 3-years-old children can decide what is their favorite toy.Well, sometimes children cannot decide, but that is a different issue.
The hard part on this problem seems to be how to explain what we do in our minds. Some people have said that we need to compare all things to all things. But that is not the case, since we only need to compare to the best-so-far option. Imagine how fat you would be if you had to eat all food in order to decide which one is your favorite dish.
So the hardness of this problem is understanding yourself, observing yourself as you make decision, and describe this in simple terms. This capacity is highly valuable. It will allow you to be a better boss, to define better laboratory protocols, or to do sport better. At the end, computational thinking is about communication, with the computer, with other users of the program, and with yourself.
There are, in fact, much harder problems. For example
- Instead of finding the largest element of a vector, sorting the vector from smallest to largest.
- Finding the smallest value of a continuous function. That is, a function defined by a mathematical formula. For example, how do we find the values of \(x\) and \(y\) that minimize \[f(x,y)=x^2+4x+y^4-5y-3xy\]
- Finding the minimal value of the same \(f(x,y)\) with additional restrictions such as \(x+y=8.\)
- Finding all the roots of any real polynomial \(f(x).\)
- Finding the first thousand (or more) digits of \(e, \sqrt{2}, \pi\) or any other irrational number.
These problems are hard to program, but people have already solved them. There are known solutions for all of them, that anybody can learn.
In 2003 the Russian mathematician Grigori Perelman solved one of the Millennium Problems, but rejected the million dollars. He also rejected the Fields Medal (which is the Nobel Prize of Mathematics), resigned from the university, moved out of the city and isolated from other people. He rejects interviews and journalists. Apparently being famous was the biggest problem for him.
On the other side, there are other much harder questions that (almost) nobody has solved. In the year 2000, the Clay Mathematics Institute proposed eight problems for the Millennium Prize. If you solve any of these problems they give you 1 million dollars. Only one person has solved one of these problems.
Other computational problems
Outside the scope of this course
- Image recognition. Twenty five years ago me and my friends worked on a system to find people’s faces in a photo. We used very expensive computers and it took a lot of time. Now your cellphone can recognize you and your friends in less than 1 second.
- Scheduling. Every year we need to organize the exam calendar. Doing it manually is hard and usually results in problems. For example, some people get two exams in one day, maybe even at the same time. With a good program these issues can be minimized, but not always avoided. This problem is hard.
- Traveling salesman. Imagine that you work for a company and you must visit each city in Turkey. Without a plan, this would be very expensive. It is better/faster/cheaper to organize the tour in a way that the sum of all trips is the smallest possible. Bad news: this problem cannot be solved by any computer in less than a century. But we can quickly get almost perfect solutions. This problem is also hard.
Real life problems
The really hard problems have little to do with computers, and are very practical. Some really hard practical problems include:
- Decide if you should register in the university and study, or instead get a job right now. The richest people in the world, such as Bill Gates, the Google founders, the Facebook guy, the Oracle guy, the Virgin guy, and so, never finished the university. They say that, if they had, they would not be as successful as they are now. But maybe this is only valid if you were born in California and your parents are already rich.Every month in the university is a month you do not get paid. You may fail in the university, and lose all that time. If you finish, maybe the job will not be well paid, especially if you had bad marks in your courses.
- Passing all courses in the university with good grades. If the courses are good, passing them is hard.
- Learning the important concepts form each course. Sometimes we memorize enough to pass the exam, but we do not learn. Then the course is time lost.
- Finding a job. Ideally we want a job that have five characteristics: well paid, entertaining, fulfilling, stable and where we know what to do. Most jobs only have three of these characteristics. Some have less.
- Moving to another country. Sometimes the best jobs are far away. We have to choose between being close to our family versus having a good job that fills our soul. Both options have good and bad parts.
- Find how to teach essential life lessons to students that do not care. Figure out how to teach them to be good scientists, or good professionals, or at least good citizens.
- Decide when to get married, and who to marry. As Elvis said, “only fools rush in”. And when we are in love, we do fool things. If you decide too soon, it may get to the next problem. Maybe if you wait a little you may find a better spouse.
- Deciding if you should divorce. We all know people that had divorced. It may happen to us. In these cases people can make irrational decisions that may be painful in the long term.
- If you are very rich, what to do with the money is a very hard problem.
- If you are poor, how to get enough money in an honest and healthy way is a hard problem.
- The hardest problem seems to be how to do what you want to do with your life.
- In fact, the hardest one is deciding what do you want to do with your life.
Can you imagine other real-life problems that do not have easy answer?
The issue here is that each person may have a different solution to every problem, since everybody is different. The circumstances are not the same, and they are not clear. We do not know all the options; we do not know all the consequences; Not all problems have a solution. Some problems have several solution. In these cases people may disagree on what is the solution.we do not know if there is a solution. And if we do not solve the problem, we create another problem.
In contrast, the problems we discuss in class are well defined, have clear consequences, and have at least one correct answer. They are easy problems. Moreover, the strategies that we learn to solve problems can also be used to real-life problems. This is our goal: to learn how to solve problems.
Molecular Biology problems
Let us go back to something “practical”. If we think about Science in general, and Molecular Biology in particular, there are some key hard problems that do involve computers.
- How to sequence DNA. The machines produce chromatograms or huge videos that have to be transformed into short sequences of letter, called reads
- How to assemble the chromosome by combining millions of reads. You can assemble 20 reads by hand, but not 2 million.
- Once you get the chromosome, how do you find the genes
- How do you compare the genes between organisms
- How do you identify the organism. In other words, how do you locate the organism in the taxonomic tree
- How do you identify the function of a gene
- How do you identify the regulatory network of the cell
- How do you identify the metabolic network
- How do you determine what would be the effect of a gene knock-out or an antibiotic
- How to measure gene expression to verify that the gene knock-out works as expected
- How to find what are the metabolites in the cell and measure their concentration
As you can see, the hard problems are also the interesting problems.
Inverse problems
Some hard problems come from undoing something easy. For example
- Division: find \(x\) such that \(a\cdot x=b.\) The input is \((a, b)\)
- Square root: find \(x\) such that \(x^2=b.\) The input is \((b)\)
- Factorization: find two integer numbers \(x\) and \(y\) such that \(x\cdot y=b.\) (All internet security—banking, e-commerce, etc—is based on this)
- Matrix inversion: find a matrix \(X\) such that \(AX=B.\) The inputs are two matrices \(A\) and \(B\)
- Integration: given a function \(f(t),\) find the function \(g(t)\) such that \[\frac{dg}{dt}(t)=f(t)\]
- \(35/2=17.5,\) not integer
- \(35/3=11.666\ldots,\) not integer
- \(35/4=8.75,\) not integer
- \(35/5=7.\) Good!
Thus, we found that \(5\cdot 7=35.\) Try to do that for \(2^{532}-1.\)
All these problems have a common characteristic. They all can be solved by brute force, that is, by trying all the alternatives. For example, to find the integer factors of 35, we can try different values of \(x\in \mathbb{N}\) and see if \(35/x\) is integer.
In other words, it is easy to write a simple program that can “solve” the problem by testing all the options, one by one. Does that means that our internet banking is in danger? No, since easy to write does not mean easy to solve.
All problems can be solved using brute force, given enough time. Some problems have shortcuts, such as method to find the square root or to divide numbers. Some problems that do not have any known shortcut are called NP-complete problems. We do not know if someday we will find a shortcut for these problems, or if it is impossible. So the hardest problem of all problems is to prove that there are no shortcuts for NP-complete problems, or to find a shortcut for any of them.
The issue is that there are too many options, so these simple programs will take a lot of time to find the solution. We are speaking of years, centuries or sometimes more than the age of the universe.
Speaking of the universe, there is a puzzle invented by the French mathematician Édouard Lucas in 1883, called “Tower of Hanoi”. It has three rods and a number of disks of different sizes. You can see the details on Wikipedia. To promote the toy and increase the sales, a story was created:
“Somewhere in the mountains there is a temple with a big version of this puzzle, with 64 disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time. According to the legend, when the last move of the puzzle is completed, the world will end.”
We can write a program to solve the puzzle. It is the kind of problems we have solved in previous years. Shall we solve it? If we write the program, and we use it to solve the puzzle with 64 disks, will the universe end?