Hacker News new | ask | show | jobs
by ColinWright 5152 days ago
It certainly wasn't intended to be condescending, I just genuinely don't understand the question.

  > When we discuss solving whether P=NP,
  > are we talking about a theoretical
  > shortcut that allows us to not have
  > to calculate everything?
I can't find any way to answer this question. We are asking whether there is an algorithm that solves a problem in NPC in polynomial time. I don't understand the question about a "theoretical shortcut," nor what it means not to have to "calculate everything." I am assuming there is a sensible question in the OP's mind, but it's not expressed in a way that makes sense to me. That's why I tried to state the question clearly and succinctly, to provide a basis for a follow-up question from the OP.

  > Or is it quantum computing that simply
  > allows us to efficiently just compute
  > everything because no shortcut is
  > likely to be discovered?
We're not talking about quantum computing, we are talking about classical algorithms.

Does that help?
1 comments
tolmasky 5152 days ago
I made a few edits to my original post as upon further reading (before you posted your reply), I did not find it condescending and in fact thought you did kind of answer him.

Also, I feel a little weird replying here since it was indeed the OP's question and not mine, but I'm kind of curious about this too now, so just know that this obviously just represents my own thoughts:

The OP's question was simply phrased in a non-mathematical way (something you will have to get used to if your goal is to teach this to people who are not familiar with this problem ;) ). By "talking about a theoretical shortcut that allows us to not calculate everything", I believe he means "finding an algorithm that allows us to not have to check every possible solution in the solution-space". Kind of how binary search is a "clever theoretical shortcut" to not have to check every index of an array. A lot of problems are exponential time because you end up having to check "basically" every possible permutation. So I think he's getting at "finding a polynomial algorithm" for the problem.

The second part then proceeds to ask whether you are considering the implications of quantum computing to this problem. I guess the answer you provided is "no", but now I would like to push you a little further as you want to write a website regarding this problem, and you seem to know a lot about it, and this is certainly a question I have heard a lot. Perhaps the answer is simply "quantum computing would not affect NP problems in any practical way", or "we just don't know", both of which would be perfectly satisfactory answers.

link
ColinWright 5152 days ago
Thank you - useful feedback. I'll be looking to make changes to take your comments into account. It also gives me an excuse to get in touch with a friend who's working on quantum computing.

It's kind of a shame that it didn't get more upvotes, and hence the chance to be seen by more people. This feedback is exactly the sort of thing I was looking for. Oh well, never mind.

link