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.

  • $\begingroup$ I'm not sure this has much to do with computer science. $\endgroup$ – Yuval Filmus Apr 28 '16 at 20:44

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 bound1 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.

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

  • $\begingroup$ Unfortunately the amount of time to translate a problem into SAT does not measure the "complexity" of discovering that such a translation exists? It may just be a simple transformation with a impressive amount of bookkeeping? Similarly with algorithms, faster algorithms are not automatically the simplest conceptually. And I believe the question is on this link between conceptual complexity and computational complexity? $\endgroup$ – Hendrik Jan Apr 29 '16 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.