Fumfer Physics 34: P vs NP, Gödel, Chaitin, and Computational Limits

In this exchange, Scott Douglas Jacobsen and Rick Rosner explore the P vs NP problem and its philosophical echoes. Rosner leans toward the mainstream view that P likely does not equal NP, drawing a parallel to Gödel’s incompleteness theorems. Jacobsen expands the discussion with Tarski’s meta-language framework and Chaitin’s arguments about irreducible complexity, connecting them to both biological systems and modern AI. The conversation emphasizes that mathematical uncertainty does not endanger reality; instead, it reveals intrinsic limits on what computation can achieve. The pair illustrate this with the traveling salesman problem, an archetype of explosive combinatorial complexity in the real world.

Scott Douglas Jacobsen: Do you think P equals NP or no? P equals problems that can be solved efficiently, in polynomial time, by a deterministic computer. NP equals problems whose proposed solutions can be verified efficiently, in polynomial time.

Rick Rosner: I don’t know. It’s not something I’ve looked at recently, or maybe at all.

Jacobsen: So it’s again a deterministic computer. The question is whether problems that can be solved efficiently are equivalent to problems whose solutions can be verified efficiently. The vast majority of people say no, but we don’t know.

Rosner: I’d lean toward no, though that is a mainstream view rather than a Gödelian one. Gödel said there are things in math that may not be provable one way or the other. That’s Gödel’s incompleteness theorem, right?

Jacobsen: Yeah, that’s true. There are three viewpoints—Tarski, Chaitin, and Gödel. Gödel is the most famous, but I think Chaitin is the one who deals with complexity—specifically algorithmic information theory and limits on provability expressed in terms of description length rather than biological complexity. He shows that certain facts about mathematical objects can be unprovable because proving them would require more information than a given formal system can encode. And Tarski showed that in a set-theoretic or mathematical system, truth for that system cannot be defined within the system itself, requiring a meta-language.

Rosner: But then you get a sort of—anyway, my answer in general is that yes, these things exist as part of the mathematical world we’re in, and they probably have real-world equivalents, but they don’t blow up the world. I don’t think there’s anything in math that makes math catastrophically inconsistent. I believe the four basic functions on a basic calculator rest on standard arithmetic, which is consistent relative to widely accepted axioms such as ZFC, and within that framework, operations like addition, subtraction, multiplication, and division are well-defined and do not yield contradictory results when rules are applied correctly. At least that fundamental structure hangs together. And there may be more obscure areas of math where, A, you can’t prove anything, and B, in the more dire sense, you might not be able to establish a consistent foundation. But maybe not. Gödel just said there’s stuff you can’t prove one way or the other within a given sufficiently strong formal system. In any case, none of this creates a tear in the fabric of reality that eventually sucks everything into oblivion. And yes, some problems are fantastically hard to calculate definitively. The easiest and most famous problem that creates computational nightmares is the traveling salesman problem, where a salesperson starts in Pittsburgh and has to travel to N other cities—maybe back to Pittsburgh, maybe not, it doesn't matter, it's the same problem.

What is the shortest path that gets them to all the cities? That turns out to be a problem where computing the optimum path requires algorithms that grow exponentially in the worst case, and no polynomial-time algorithm is known for solving it exactly. It’s highly resistant to shortcuts. The more cities you add, the more computation you burn trying to reach the definitive optimal solution. It’s a huge computational problem if you insist on the absolute optimum. But you can also say “forget it,” once you get a solution that seems pretty good. If the salesperson has to travel to 35, 55, or 105 cities, you can take reasonable guesses about what might be a short route. You can sketch it out, or sketch out fifty different versions—which is easy for a computer. Probably none of them will be perfect, but they’ll cluster very close together. In many practical settings, heuristics and approximation algorithms find routes that are extremely close to optimal, sometimes within 1 percent of the true shortest distance. So you can say, “All right, here’s an order of cities, and it’s pretty good.” And the salesperson can ask, “But is it the shortest path?” And the boss can answer, “Maybe. Probably not. Just go sell your stuff and don’t worry about it.” Issues like this matter, but the world doesn’t depend on them.

Rick Rosner is an accomplished television writer with credits on shows like Jimmy Kimmel Live!, Crank Yankers, and The Man Show. Over his career, he has earned multiple Writers Guild Award nominations—winning one—and an Emmy nomination. Rosner holds a broad academic background, graduating with the equivalent of eight majors. Based in Los Angeles, he continues to write and develop ideas while spending time with his wife, daughter, and two dogs.

Scott Douglas Jacobsen is the publisher of In-Sight Publishing (ISBN: 978-1-0692343) and Editor-in-Chief of In-Sight: Interviews (ISSN: 2369-6885). He writes for The Good Men Project, International Policy Digest (ISSN: 2332–9416), The Humanist (Print: ISSN 0018-7399; Online: ISSN 2163-3576), Basic Income Earth Network (UK Registered Charity 1177066), A Further Inquiry, and other media. He is a member in good standing of numerous media organizations.