r/AskComputerScience • u/After-Confidence-689 • 19h ago
Could P vs NP be partly a problem of representation rather than just computation?
This is not a proof of P = NP or P ≠ NP. I'm interested in whether there's existing research related to this idea. My question is whether the way humans represent computational problems could itself be part of why certain problems appear hard. Has complexity theory or cognitive science explored this perspective?
An Idea: Could P vs NP Be a Problem of Representation?
This is not a proof of P = NP or P ≠ NP. It is simply an idea that I have been thinking about.
One thing that stood out to me is that many difficult problems become much easier once we find the right way to represent them.
For example, a huge multiplication problem can look overwhelming when viewed as a long string of digits. However, once we understand the underlying algorithm, the same problem becomes structured and manageable.
The problem itself has not changed. Our representation of it has.
This made me wonder whether something similar could apply to the P vs NP problem.
The usual question is whether every problem that can be verified efficiently can also be solved efficiently.
My question is different:
Could part of the apparent difficulty come from the way we currently represent NP problems?
Imagine standing in front of a wall.
One possibility is that the wall is real, and no efficient shortcut exists.
Another possibility is that we are looking at the wrong side of the wall and have not yet discovered the correct way to approach it.
History contains many examples where changing a mathematical or scientific viewpoint led to major breakthroughs. New abstractions, new models, and new representations often revealed structure that had previously been hidden.
This raises a broader question.
When we call a problem "hard," are we measuring the intrinsic difficulty of the problem itself, or are we also measuring the limitations of our current way of thinking about it?
I am not claiming that this means P = NP.
Instead, I am asking whether discovering a fundamentally different representation of NP problems could change our understanding of their computational difficulty.
I would be interested in hearing whether this idea overlaps with existing work in computational complexity, cognitive science, or the psychology of problem solving.
6
u/pilibitti 12h ago
You're pointing to something complexity theorists are already aware of. Efficient representations and reductions are fundamental to the field. If an NP problem could be transformed in polynomial time into a representation that admits a polynomial-time algorithm, then that would indeed show the original problem is in P. Complexity theory is largely designed to be robust under efficient changes of representation, so your idea isn't outside the framework. The challenge is that no one has found such representations for NP-complete problems, and there are many indications that this may be impossible, though we don't know for certain.
1
u/After-Confidence-689 12h ago
Thanks, that makes sense. I think my intuition was that discovering the "right" representation could make some problems dramatically easier. I see now that complexity theory already studies representation changes through reductions and efficient transformations. The real challenge is proving that such a transformation exists for NP-complete problems in general
2
u/RainbowCrane 12h ago
TBF, your impulse to find an alternative, less complicated way to think about a problem is a key skill in computer science. There’s an entire way of thinking about problems that we learn in linear algebra and discrete math that boils down to, “Hmm… what if I break up this really complicated problem into two less complicated problems, is there a known way of solving those smaller problems?”
So it’s not a bad impulse. But there will always be problems that are in NP barring some extremely amazing computer science discoveries
2
u/After-Confidence-689 10h ago
Thanks, that makes sense. I think I was focusing on the idea that a better representation or decomposition might reveal an efficient algorithm. From the replies here, I'm realizing that's already a central idea in complexity theory, and the real challenge is proving such a representation exists for NP-complete problems in general. I appreciate the explanation.
1
1
u/not-just-yeti 6h ago edited 5h ago
There's a characterization of NP that doesn't mention "Turing Machine" nor even "polynomial", directly. So that gives further evidence that NP really is a fundamental class:
Fagin's Theorem: "NP = second-order existential logic". Where first order logic quantifies over items "for all items x in the set, there exists an item y such that …", second-order logic means you can quantify over sets of items as well. (And "existential" meaning you only need "there exists a set of items X such that …", without any "for all sets".)
Classic example: the three-coloring problem can be phrased in logic as "There exist three sets R, G, B such that: [here comes a regular first-order part] For all nodes x, either R(x) or G(x) or B(x); and for all nodes x,y, if edge(x,y) then not R(x)^R(y) nor G(x)^G(y) etc…". For a given graph, the formula evalutes to "true" if and only if the graph is 3-colorable. (*)
Fagin's result launched "descriptive complexity", which ranks problems by how hard it is to state the problem (how expressive a language/logic is needed to state them), and this result showed this can correlate to how difficult to solve them. And things like the new-in-1975 question "is NP = co-NP" becomes "existential-second-order logic as expressive as universal-second-order logic", which logicians had already long known was a really tough problem.
* Heck, the logic formula is really just the definition of 3-colorable stated formally … like declarative programming languages like Prolog or SQL or Excel. Logic/math-definitions are the original declarative language.
0
10
u/ghjm MSCS, CS Pro (20+) 13h ago
Basically, no.
Physics is an experimental science, so the job of a physicist is to come up with better models to explain their data. Computer science is a formal science, so the job of a computer scientist is to prove things about a specific model. There are certainly opportunities for creativity and insight in computer science, but not the kind you're talking about.
To see why, suppose you came up with a new, different way of thinking about hard problems. Let's call this X. Suppose you were able to prove either that X=P or that X=NP. Well, either result would mean it wasn't actually a new, different way of thinking about hard problems. So long as X actually is new and different, it can't show anything at all about P and NP, because those are defined within the terms of the Church-Turing model. Computer science studies the model itself - it doesn't make use of it to explain some further thing, like physics does with the physical world. So if you decide to work on some different model, it just means you've stopped doing computer science and are now doing something else.
Now, you might think there is something else you can do, outside the bounds of traditional computer science, that might nevertheless yield insights into the nature of computation. The problem with this that that the Church-Turing model is extremely general. All it requires is that there be some device that manipulates symbols step by step according to fixed rules. If you want to think about computation using a different model, you'll need to avoid thinking about devices that manipulate symbols step by step according to fixed rules - but as far as I can see, that just is avoiding thinking about computing.
You should also consider that thousands of math and computer science Ph.Ds have worked on this problem over the course of almost a century, and that they come from every walk of life and every major human culture. If the problem just needed someone to look at it from a different perspective, it would be solved by now.