[gauravk92]

When we discuss solving whether P=NP, are we talking about a theoretical shortcut that allows us to not have to calculate everything? Or is it quantum computing that simply allows us to efficiently just compute everything because no shortcut is likely to be discovered?

[ColinWright]

Thanks for your response, but I'm having trouble making out what your actual question might be. Let me set the scene:

The class P is those problems that can be solved in polynomial time.

The class NP is those problems such that an alleged solution can be checked in polynomial time.

Every problem in P is also in NP.

We don't know if there are any problems in NP that are not also in P. That's what we want to know.

So given that, what was your question?

[tolmasky]

This was kind of a strange way to answer the OP's question, although I think you did answer it. I believe he was asking whether "solving NP" means "finding polynomial time solutions to NP problems" (the traditional way to "solve" P?=NP) or "creating machines that through quantum magic can simply plow through NP problems despite not having a polynomial time algorithm for them".

I think the OP assumes that a quantum computer would indeed be able to do this, but I don't know whether that premise is true or not. I have heard this question phrased often times as "Does P=NP still matter in a world of quantum computers?". As I am not an expert on either P=?NP or quantum computing, I have no idea.

So, given that, it seems you are affirming that you are referring to just the P?=NP question and not the "practical" question of whether we can get around this through other means (such as quantum computing).

Edit: revised first sentence since I now think you answered his question.

[ColinWright]

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?

[tolmasky]

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.

[ColinWright]

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.

[pjscott]

Check out the BQP complexity class:

http://en.wikipedia.org/wiki/BQP