Computer science seems to be on an unstoppable curve of progress. From vacuum tubes to microchips, dial-up to high-speed Internet, and Office Assistant Clippy to ChatGPT in just a few decades. But thousands of everyday problems across science and industry remain as unsolvable for today’s AI-powered supercomputers as ever.
These difficult “NP-complete” problems are promised a million-dollar prize by the non-profit Clay Mathematics Institute if you can find a quick solution or prove that no solution exists. A surprising insight from the 1970s makes this challenge even more fascinating. These over a thousand problems are, in a deep sense, one and the same. Solve one and solve them all. This concept is currently fundamental in the field of theoretical computer science, showing that certain groups of computational problems form a unified web. Discovering fast algorithms that solve Sudoku puzzles of any size will help you break through the encryption schemes that protect our digital economy. Once we uncover a shortcut to scheduling a flight tour on a budget, you can use it to solve almost every famous unsolved math problem.
Finding fast algorithms for these NP-complete problems (or proving that no such algorithms exist) solves one of the most important mysteries in computer science: P vs. NP. P refers to the set of computational problems that computers can solve efficiently. NP, on the other hand, represents a problem that has a possible solution. Verified efficiently. However, these problems cannot always be resolved quickly. NP includes everything in P (because finding a solution is a perfectly good way to test it), but also includes more difficult problems for which we don’t know how to do it efficiently. find Solution. Only after the issue is resolved can it be verified. The P versus NP question asks whether this apparent asymmetry between solution discovery and solution validation is real or illusory. Perhaps P = NP and they refer to the same set of problems. In other words, an NP problem that we don’t know how to solve efficiently is probably appear It is more difficult than the P problem because the appropriate insight has not yet been found.
About supporting science journalism
If you enjoyed this article, please consider supporting our award-winning journalism. Currently subscribing. By subscribing, you help ensure future generations of influential stories about the discoveries and ideas that shape the world today.
For example, given a large list of cities, flights connecting them, and a budget, an algorithm (recipe for easy instructions) that efficiently determines whether you can visit all of them while still respecting your budget is Is there? I don’t know. we know inefficient Algorithm: Checks all possible sequences of flights visiting all cities, adds up the cost of each, and compares the sum with your budget. However, as the number of cities included in the list increases, the number of routes to check explodes and quickly becomes infeasible even on the fastest computers. There may or may not be a clever shortcut to bypass this exhaustive search, but computer scientists haven’t found it yet. given solutionHowever, in this case, the list of proposed flights allows you to verify in a reasonable time whether the route passes through all cities and falls within your budget. If P equals NP, it means that there is a quick solution to the flight scenario (an example of the so-called traveling salesman problem). I don’t know that yet.
Many natural computational problems join the traveling salesman problem in the NP set. This includes logistics (like packing boxes into a truck), social networks (finding a group of friends in common), biology (predicting how proteins will fold), and Sudoku, Pokemon, and Candy Crush. Contains challenges from games such as. Mathematics itself can also be cast as an NP problem, since proofs can be verified efficiently. It may seem strange to classify these as “hard” problems when people pack boxes into trucks and solve Sudoku every day. However, we believe that the algorithm solved the problem efficiently only If that gets resolved every Run your instances efficiently, including very large ones. Of course, a computer can solve a 9×9 Sudoku faster than a 1 million x 1 million Sudoku, so the strict definition of “efficient” depends on how much time it takes to solve the problem, depending on the size of the input. It shows how proportional it is.
Since the P versus NP problem is about different computational problems and how they are related to each other, it seems to me that these problems need to be investigated separately to be solved. Maybe. Suppose you discover an efficient algorithm for the traveling salesman problem. That’s a heroic advance, but does it tell you anything about your ability to solve giant Sudoku or other difficult NP problems? Amazingly, the algorithm for that single problem is completely resolved. In 1972, computer scientist Richard Karp published a seminal paper demonstrating that 21 classical NP problems have remarkable properties. This means that an efficient algorithm for solving one of them will not only solve the other 20 problems; every NP problem. He called these 21 problems NP-complete. The list has grown in the intervening years, as researchers have discovered many other NP problems (including the traveling salesman problem) that share this magical property.
NP completeness can be viewed optimistically or pessimistically. Optimistically, between us and the possibilities of unknown technology stands a fortress of monumental problems, now like a house in the sand. As we pull into the realm of possibility, the entire NP edifice collapses, and a scientific revolution rises from the rubble, filled with effortlessly efficient transport, rapid drug discovery through protein folding, and a new era of mathematics. . While pessimistic, NP-completeness suggests that there are no efficient algorithms for these problems. If all it takes to prove otherwise is to overcome a single problem, why hasn’t anyone succeeded yet? Most experts lean toward the latter interpretation, suggesting that NP-complete I suspect that there is no fast algorithm for the problem.
Whether the glass is half-full or half-empty, the concept of a complete problem has changed the way researchers look at computation. Karp first demonstrated that an algorithm for one NP-complete problem could be used to solve another NP-complete problem by demonstrating that seemingly unrelated problems could be translated into each other’s languages using a process called NP-complete problems. We have shown that it can be solved. reduction. It works by showing you how to take an instance of one problem (such as a list of cities, flights between cities, or a budget) and transform it into another problem (such as a large Sudoku puzzle). Sudoku has a solution that only works if you can visit all cities within your budget (otherwise there is no solution). In doing so, if you discover an efficient algorithm for Sudoku, you can also use that algorithm to solve the Traveling Salesman problem by converting instances of the Traveling Salesman problem into Sudoku puzzles. can. (See the end of this article for a detailed example of reduction.)
This ability to encode one problem using another language is not only a feature of this example, but also of the computation itself. A web of reductions combines all NP-complete problems. Solving one will also solve the other NP problems. Its influence confuses the mind. Recall that the proof of a mathematical theorem can be framed as an NP-complete problem. Choose a famous unsolved math problem. The theory of NP-completeness states that there exists some level of Candy Crush that completely encodes the math question. If a certain score can be achieved in a certain number of moves on that level of Candy Crush, then the math problem has a proof of a certain length. Otherwise it is not. NP-completeness also ensures that certain advances in protein folding (or box packing or Sudoku solving) can disrupt the digital economy. That’s because encryption, which protects sensitive data, works by keeping it behind computational problems that are considered difficult to solve. (Note that while solving an NP-complete problem can break an encryption, the converse is not true. The intractable problem underlying most encryption schemes is itself not completely NP-complete. )
Since all of this is based on an NP-complete problem, $1 million for a solution may seem like a bargain. And who knows, you might just be able to use a little extra motivation the next time you’re struggling to plan a vacation trip or solve a Sudoku puzzle.
How does reduction work?
For those who want to learn more about how reduction works, let’s reduce another type of NP-complete problem, the “map three-color problem,” to a “clique problem.” The three color coded map questions ask the following questions: Given a map, can one of three colors be assigned to each region so that adjacent regions do not repeat the same color? , does the network include the required number of groups of people who are all mutual friends? Both problems are NP-complete. That is, I don’t know of an efficient algorithm in either case. On the surface, they have little in common. However, we can transform the given map into a social network and show that the answer to the social network problem yields the answer to the map problem.
Think of a map of the United States. Designate three “people” in each state to build your social network from there. Assign one person to each color: blue, green, and red. Then we can be friends Unless:
-
They represent the same state. (Green Wisconsin representatives will not be friends with blue Wisconsin representatives.)
-
These have the same color and represent neighboring states. (North Dakota and South Dakota share a border, so red representatives will not become friends, but North Dakota and Florida do not share a border, so red representatives will not become friends.) )
I argue that this social network of 150 people includes a group of 50 mutual friends only if the map of the United States is colored in three valid colors. If you find 50 mutual friends in your network, they should all represent different states. Because by design, people who represent the same state cannot be friends. Additionally, coloring for cliques never assigns the same color to adjacent states. We expressly prohibit such links within our network. Therefore, a population of 50 people corresponds to three valid colors. Similarly, if there are no 50 cliques in the network, there will be no three colors in the map.
we just decreased From three-color map problems to clique problems. This means that if someone discovers a fast algorithm for the clique problem, they can use it to solve every instance of the three-color map problem. Importantly, the first step (transforming the map into a network) is fast. Creating suitable friendships with people in your network does not require exhaustive searches or other unfeasible computational overhead. Reduction shows us that even if we feel like our problem is unique, it may be more universal than it seems.
This is an opinion and analysis article and the views expressed by the author are not necessarily those of the author. scientific american.
