Are all problems approached and solved in fundamentally the same way?

Question

This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot.

This questions stems from a conversation a friend and I were having about the google interview process. It boiled down to my argument that they are searching for individuals who are fundamentally better problem solvers than others (His argument is that prior job experience proves this, mine is that it doesn't).

This got me thinking. Say we want to solve a simple problem 2 + 2, we could go about this the simply way and just count 1 2, 3 4 to get to the answer or we could chose a much more complex way to arrive there. I argue that both ways fundamentally solve the problem the same way; that the more complex solution is reducible to the simplest.

This linked up in my brain to Big O. It has been shown that all problems in NP are equivalent and can be translated (reduced?) to each other (I might be completely wrong on this); essentially if you solve one (in P time) you solve them all. It kind of shows to me that all problems within their given class are fundamentally the same.

This leads me to question, is the way that problems are solved fundamentally the same? Moreover, is there a way to solve all problems (nothing about running time)?

Again disclaimer, not a full complete thought. I just wanted to get it out there before I forget it and never think of it again. I found it interesting enough to share and just wanted input. Please correct if (where.) I am wrong.

Answer 1

What you're missing is that, although all NP-complete problems can be reduced to one another, so it is true that solving one lets you solve them all, that doesn't mean that they're all equally easy, so they're not all "the same problem".

In particular, the reduction takes some amount of time to perform. Although all problems in NP can be reduced to, say, SAT, that doesn't mean that all problems in NP are as easy as SAT. Some require very little effort to translate to SAT; others require much more effort. And there's no bound¹ on how much effort might be needed, as you look at more and more complex problems within NP.

A way to make this concrete is with the time hierarchy theorem. That says that, essentially, allowing more time for computations lets you compute more things, and it applies to nondeterministic machines as well as deterministic ones. So, solving SAT instances takes some amount of time but, if you allow yourself more time than that, you can solve strictly more things.

---

¹ OK, its always a polynomial but there's no bound on the degree of that polynomial.