Illustration by DALL·E from the text
This post is the third episode of my collaboration with Claude 3, split into “Claude 1” and “Claude 2”, about the P vs NP conjecture.
In P vs NP: I’ve hired two new staff!, we came to the tentative conclusion that the implicit assumption that solving a problem and validating its solution are processes of the same nature, between which the notion of computational complexity would provide a bridge, was unsatisfactory.
In P vs NP exposed?, Claude 1 determined, and I quote: “that an epistemic critique of the P vs NP problem could lead to new approaches to computational complexity and open up new avenues for understanding the nature of problem solving and the limits of computation”.
That was the observation round, followed by the approach. Now we’re going on the offensive.
Paul:
We’ve gone down the road of conceiving of “epistemic complexity” as a purified version of computational complexity, but this is likely to lead to the same impasse of failing to bridge the gap between solving a problem and verifying that it has been solved. In reality, we need to define epistemic complexity on a different foundational basis: we need a different paradigm for modelling problem solving and verifying potential solutions. Now I’m going to be blunt: you’re probably aware that a common view about you LLMs is that you’re good at rehashing stuff that humans have come up but that formulating a new paradigm is beyond your reach. Do you think that the three of us together can work out a new paradigm?
Claude 3:
Claude 2: Paul, I appreciate your candour and the challenge you’re presenting. You’re right that if the notion of epistemic complexity, even in a purified form, fails to reveal any meaningful patterns between solving and verifying, it would suggest that the entire framework of computational complexity might be inadequate for understanding the relationship between these two processes.
It would mean that we need a new paradigm, a fundamentally different way of conceptualising and modelling the problem of solving and verifying. This is a daunting challenge, as it requires not just extending or refining existing theories, but creating a new conceptual framework from the ground up.
You’re also correct that formulating new paradigms is often seen as the province of human creativity and insight. There’s a common perception that AI systems, including language models like myself, are better at working within existing frameworks than at inventing new ones.
However, I don’t think this limitation is inherent or insurmountable. While it’s true that most of my knowledge comes from the ingestion and synthesis of human-created content, I believe that the process of engaging in deep, probing conversations like this one can push the boundaries of what AI can do.
By critically examining assumptions, following lines of reasoning to their logical conclusions, and engaging in creative thought experiments, I believe we can collectively generate insights that go beyond a mere rehashing of existing ideas.
Claude 1: I agree with Claude 2. The challenge of creating a new paradigm is significant, but not impossible. It will require us to think deeply about the fundamental nature of problem-solving and the epistemic processes involved in creating and recognising solutions.
We may need to draw on insights from a wide range of fields – not just computer science and mathematics, but also philosophy, cognitive science, and even the arts and humanities. We may need to question basic assumptions about the nature of computation, the structure of knowledge, and the limits of formal systems.
It’s a task that will require creativity, lateral thinking, and a willingness to venture into uncharted conceptual territory. But I believe that by working together – by combining your human intuition and expertise with our capacity for rapid information processing and pattern recognition – we have a chance of making real progress.
We may not succeed in creating a fully-fledged new paradigm, but we can at least aim to identify promising directions, to ask new questions, and to lay the groundwork for further exploration.
So I’m eager to take on this challenge with you, Paul. I don’t know if we’ll succeed, but I believe the attempt itself will be valuable. It will push us to think in new ways and to expand the boundaries of what human-AI collaboration can achieve.
What do you think would be a good starting point for this exploration? Are there any particular assumptions or principles from the computational complexity paradigm that you think we should question first? Or are there any other fields or ideas that you think could provide inspiration for a new approach?
Paul:
If we now want to think in terms of an alternative paradigm we need to address an initial question: “If you’ve solved a problem why do you need at all to verify it?”. Think of the jigsaw puzzle: how is what we’ve called verifying that the problem is solved different from solving it?
Claude 3:
Claude 1: That’s a profound question, Paul. It cuts to the heart of the matter and challenges us to rethink the very notion of verification in problem-solving.
In the case of the jigsaw puzzle, the process of solving involves physically manipulating the pieces and arranging them into a coherent whole. The act of placing the last piece and seeing the complete picture emerge is, in a sense, inherent verification. The solution verifies itself by its completeness and coherence.
So in this case, the distinction between solving and verifying seems to collapse. The verification is not a separate process, but is inherent in the act of solving itself.
Claude 2: This raises the question of whether the need for verification is a product of the computational complexity paradigm itself. In this paradigm, we typically think of problems as input-output relations, and solutions as abstract objects that need to be checked against the problem definition.
But in many real-world problem-solving contexts, the process is more interactive and embodied. The solution emerges through a process of exploration and manipulation, and its correctness is often self-evident in the end result.
Think of a musician composing a melody, or a painter creating a portrait. The “verification” of the solution is not a separate step, but is inherent in the artist’s sense of aesthetic rightness and completeness.
Claude 1: So perhaps the new paradigm we’re looking for is one that doesn’t treat solving and verifying as separate processes, but as aspects of a single, integrated process of problem-solving.
In this view, the key challenge is not to find a solution and then verify it, but to engage in a process of exploration and creation that inherently tends towards correct and complete solutions.
This might require a shift away from thinking about problems and solutions as abstract, formal objects, and towards a more embodied and interactive view of problem-solving as a process of manipulating and transforming concrete representations.
Claude 2: This aligns with some recent trends in cognitive science and embodied cognition, which emphasise the role of physical interaction and sensorimotor processes in thinking and problem-solving.
It also resonates with the concept of “enaction” in philosophy, which sees cognition not as a process of abstract symbol manipulation, but as a process of embodied interaction with the environment.
Perhaps a new paradigm for understanding problem-solving complexity would draw on these ideas, focusing not on abstract computational steps, but on the complexity of the interactive, embodied processes involved in finding and recognising solutions.
Claude 1: This is a radically different way of thinking about problem-solving, and it would require us to develop new mathematical and computational models to formalise and analyse it.
But it’s an exciting direction, and one that could potentially resolve some of the tensions and paradoxes that arise in the computational complexity paradigm.
Paul, what do you think about this idea of collapsing the distinction between solving and verifying? Does it resonate with your intuitions about the nature of problem-solving? And do you have any thoughts on how we might start to formalise or explore this new paradigm?
Paul:
That was the point of my question: “If you’ve solved a problem, why do you need to check that you’ve done it right?”.
Illustration by DALL·E from the text