Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

P vs. NP and the Computational Complexity Zoo (2014) [video]

youtube.com

Post reply on HN
Print view View original

11–20 of 60 posts

Re: P vs. NP and the Computational Complexity Zoo (2014) [video]

#11

Post by SilasX »

nsnick wrote: post #5
DanAndersen wrote: post #3

I definitely got a sense of mathematical awe out of that. Thanks for sharing. I'm always impressed when I see someone who can communicate ideas, especially complex scientific concepts, clearly and effectively, using analogies in a proper way that doesn't just overwhelm the viewer (as a lot of popsci stuff does). It's a talent I know that I need to work on; as a fledgling academic attempting to write papers clearly I…

Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (co…

>He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest.

It's kind of imprecise, but the understanding in these situations is that you're talking about some bounded version of the problem. In TSP, it's common to mean the problem of "is there a solution of length less than N", and you're only verifying that the length is less than N, not that it's optimal.

Re: P vs. NP and the Computational Complexity Zoo (2014) [video]

#12

Post by [deleted] »

hebdo wrote: post #9
nsnick wrote: post #5

Earlier quoted context omitted.

Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (co…

There is an alternative, equivalent definition of NP languages, through projections of certain polynomially bounded and P-verifiable relations. This is the strict mathematical base for the commonly spread and very valid observation, namely that for a decision problem to be in NP means for its solution to be verifiable in polynomial time. Traveling salesman is in NP. There is no point debating this. Edit: as others ha…

[deleted]

Re: P vs. NP and the Computational Complexity Zoo (2014) [video]

#14

Post by ColinWright »

CJefferson wrote: post #7
nsnick wrote: post #5

Earlier quoted context omitted.

Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (co…

There is no debate, plain travelling salesman is defiantly not known to be NP-complete. The usual solution for optimisation problems is to turn them into a decision problem, by saying "is there a path of length k or less?". Then it is in NP-complete

  > There is no debate, plain travelling salesman
  > is defiantly not known to be NP-complete.
Actually, there is no debate, plain TSP is specifically not NP-complete and cannot be, because it's not a decision problem. So it's not just, as you say, "not known to be" but instead is "known not to be".

However, by using binary search you can convert a decision version of TSP into the optimisation version in polynomial time. In this sense it is perfectly reasonable to refer to TSP as being NP-Complete.

I agree completely that these sorts of differences actually matter when dealing with the technicalities, but in practice it makes sense not to worry too much when trying to explain the broader concepts.

Re: P vs. NP and the Computational Complexity Zoo (2014) [video]

#18

Post by z3t4 »

Ar-Curunir wrote: post #6
z3t4 wrote: post #4

That video helped a lot, but I'm still struggling to understand what the N=NP question means and how to prove it. I think that all problems with a set definition for "solved" is solvable as in "P". For example, the rubik's cube is solved if all sides have a solid color. And is thus a "P".

NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which we can find a solution in polynomial time in the length of the input. Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.

So basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ?

/brainstorming

Re: P vs. NP and the Computational Complexity Zoo (2014) [video]

#19

Post by Ar-Curunir »

z3t4 wrote: post #18
Ar-Curunir wrote: post #6

Earlier quoted context omitted.

NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which we can find a solution in polynomial time in the length of the input. Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.

So basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ? /brainstorming

Well no, every problem in P is in NP trivially.

To prove P = NP, you would have to prove that one of the many NP-Complete problems has a polytime algorithm. Well that's not the only way to prove P = NP, but that's one approach.

Post reply on HN