P vs NP
In this week’s episode, host Kyle Polich interviews author Lance Fortnow about whether P will ever be equal to NP and solve all of life’s problems. At the heart of the P-NP problem is the question “are there problems for which the answers can be checked by computers, but not found in a reasonable time?” If there are such problems, then P does not equal NP. However, if all answers can be found easily as well as checked (if only we found out how) then P equals NP.
To describe the P/NP problem, Lance begins the discussion with the example question: Are there 100 people on Facebook whom are all friends with each other? Even if you were an employee of Facebook and had access to all its data, answering this question naively would require checking more possibilities than any computer, now or in the future, could possibly do. The P/NP question asks whether there exists a more clever and faster algorithm that can answer this problem and others like it. Lance thinks there is no such algorithm, and to this day, nobody knows if such an algorithm exists. Also, nobody knows of an algorithm that can solve any of its related NP-complete problems, which is why most people do think that P ≠ NP.
The P/NP problem matters because if P=NP it would make a large number of difficult computational tasks immediately easy to solve and it would not only revolutionize the tech industry but would also transform our lives radically. For example, we’d cure major diseases like cancer, make accurate predictions of weather, get near prefect translation, etc. The computer would have the ability to find solutions to virtually any question we could ask of it.
Lance thinks that solving P=NP would have quite the dramatic effect on society. However, he thinks that the significance of the P/NP question is not just about whether or not we find a solution. Rather, P/NP tells us what’s possible. Even if P and NP are different, the problems we could solve if P=NP are typically still solvable, it will just require considerably more effort and time.
Links to Check Out:
The Golden Ticket by Lance Fortnow
Computational Complexity – Lance’s long-running blog, and a great place to see what else is going on in theoretical computation.
