by Krešo Josić
Today, questions with answers that are hard to find, but easy to check. The University of Houston presents this series about the machines that make our civilization run, and the people whose ingenuity created them.
Think of an online social network. Such social networks contain groups of people who are all friends with each other. We call such groups cliques: A clique is thus a group of people where every pair is connected. Is there a clique of 100 people on Facebook? Of 1000 people? Answering these questions is hard. For large cliques and networks finding an answer is all but impossible. The problem can be too hard even for the fastest computers. And yet, once an answer is found it is easy to check: If I give you a list of 1000 people and say they form a clique, all you need to do is check that all people on the list are friends with one another.
This question about cliques belongs to a special class of problems: They are hard to solve. But solutions, once found, are easy to check. Here is another such problem: Suppose I give you a list of cities. Your task is to find a chain of one-way flights that starts and ends in Houston, and goes through all other cities on the list once. However, the total length of the trip cannot exceed, say, 10,000 miles. If I hand you a solution you can check it easily: Just sum the length of the flight segments, and check off all the cities on the list. But finding such a route, or showing that none exists is hard!
These problems are easy to understand, but hide some surprises: First, it is possible that both the clique problem and the flight problem can be solved much more quickly than we think. Maybe computer scientists and mathematicians have just not found a good way to do it yet. Figuring out whether such a faster solution is possible is related to the biggest unsolved problem in computer science, the so-called P vs NP problem.
A physical Turing machine which is used in the precise definition of complexity that is discussed in this episode. A true Turing machine would have infinite tape on both sides.
Photo Credit: Rocky Acosta via Wikipedia and is licensed under the Creative Commons Attribution 3.0 Unported license.
Even more surprisingly, a fast way of finding cliques, or airplane routs, would also allow us to more quickly solve other hard questions. Some of these are frivolous, for instance solving a Sudoku puzzle on a large grid. But other problems are very applicable. Indeed, finding such faster solutions could upend entire industries: Financial transactions over the internet are encrypted to keep them safe. But this security relies on the assumption that certain mathematical problems are hard to solve. Finding fast solutions to the clique problem could also mean that our financial transactions are no longer secure. Computer scientists would have to devise new ways of keeping communications safe. On the other hand we would be able to solve many problems much faster: For instance, companies would be able to find efficient shipping routes more easily saving energy, time and money.
Mathematics helps us shine a light on the surprising connections between different problems. It can relate puzzles that we enjoy in our spare time, to problems that have a big impact on our life. Mathematicians find such connections by getting at the essence of a problem, and by devising a language to talk about this essence. While that language may seem unintelligible, it sometimes allows us to find answers to questions that impact us all.
This is Krešo Josić at the University of Houston where we are interested in the way inventive minds work.
Computer scientists have a precise definition of what I mean by hard problems and fast solutions. For a previous episode by Andy Boyd on optimization, the P vs NP problem, and NP completeness see here. The footnotes to this episode also contain a readable discussion of the P vs NP problem, the biggest unsolved problem in computer science I mentioned in the episode. These footnotes also discuss NP-complete problems. If we find a "fast" solutions to one NP-complete problem, we will find fast solutions to all others. I mentioned two NP-complete problems in the episode. There are many others. For instance, the battleship puzzle is NP complete: here
For a list of NP complete games see here.
This episode was first aired on June 7, 2022