Starting to explain P vs NP - what do *you* find confusing? | Hacker News Reader

Starting to explain P vs NP - what do you find confusing?

penzba.co.uk

16 pointsColinWright13 comments

This is very much an early stage, but as with startups, if you're not embarrassed by it then you waited too long to launch.

My intention is to go through enough of the details to show that there really are problems that are NP-Complete, and to give enough of the details that someone truly interested in the topic has a handle on the concepts, terminology, and what to look for to get more details.

I'm interested to know what you think needs expanding or better explaining.

Let me know!

Added in edit: To whomever is trying to edit, feel free to email me for a login.

For me, P vs NP is a very clever bit of theory, and proofs of NP-completeness are actually kind of fun, but the more interesting question that it skirts is this: How do we talk about the speed of different algorithms? That's a much bigger topic, but usually a lot more relevant. If you're someone with code who's in a hurry, you benchmark as realistically as you can manage and hope you didn't flub the implementation, and that your data collection was statistically okay. If you're Donald Knuth, you define a simplified but somewhat realistic processor model and derive expressions for how much time your algorithm takes, and there's your answer. This is nice, but a lot of work, and it becomes positively nightmarish if you want accuracy on modern processors. If you're an Intro to Algorithms class, you look at the asymptotic complexity -- mergesort is O(n lg n), the (NP-complete) 3SAT problem is O(2^(n^k)) for some constant k, and so on. This gives good intuition a lot of the time, but not always. Insertion sort typically beats mergesort for small n, there are a lot of 3SAT problems that can be solved very easily, caches are all the time doing crazy stuff, and in general the world is complicated. We're interested in getting computers to solve problems in a reasonable amount of time; what are we to do?

I know this isn't exactly an answer to your question, but I really wish that people had said more about this in college, and I wanted to talk about it.

Deleted comment

Thanks for your reply ...

I need to re-write the section because really I'm dealing with Hamilton Path rather than Traveling Salesman, but even so ...

Even if you say that all inter-city routes are of unit length, it's hard to find a route that visits each city exactly once. The key point is that we're not allowed to re-visit a city. Such a path, visiting every node exactly once and returning to the starting point, is called a Hamilton Cycle, and there is no known sub-exponential algorithm to guarantee finding whether a given network (or graph) has one.

Is that clearer?

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?

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?

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.

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?

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.

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.

Check out the BQP complexity class:

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

Yes sorry, realised just before you posted that this was HPP, not the TSP subset I'm familiar with where all cities are connected by their Euclidean distance. [I deleted my original post which asked why the TSP problem was described as _a_ path, rather than the shortest.]

Not P vs NP so much, but I have a hard time keeping straight how all of the complexity regions are laid out in the global complexity space. If you could explain how they relate and make a nice picture you'd be a hero.

Reply on news.ycombinator.com