P vs. NP and the Computational Complexity Zoo (2014) [video]
1–10 of 60 posts
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#2Reddit's thread: https://www.reddit.com/r/programming/comments/372634/the_n_v...
The video is very well structured and goes from very basic explanations of the concept of complexity up to the different classes of complexities.
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#3I 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 struggle with it. Does it simply come with practice or are there resources anyone here can recommend for improving one's ability to make hard ideas understandable?
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#4That 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".
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#5I 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 (correct me if I am wrong) a problem that can only be solved in factorial time on a Deterministic Turing Machine for example cannot be part of the class NP.
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. https://www.ibm.com/developerworks/community/blogs/jfp/entry...
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#6That 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.
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#7I 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…
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
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#8I 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…
To clarify your last point, P and NP are classes of 'decision' problems, i.e. problems for which we have a yes/no answer. TSP is commonly formulated as a combinatorial OPTIMIZATION problem
The decision version of TSP would be formulated as: Given a complete graph G and a budget b, decide if there exists a path that visits each node and has cumulative weight less than b.
If you have a solver for decision TSP, then you can solve the optimization version of TSP by performing binary search on the budget b.
I'm glossing over some details, but there's a clearer explanation on how to solve search problems with an oracle for decision problems in Sipser.
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#9I 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…
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 have pointed out: traveling salesman in in NP only when it is in its decision version. Otherwise the question does not make sense, as standard complexity classes are defined for decision problems, this is - for languages.
Re: P vs. NP and the Computational Complexity Zoo (2014) [video]
#10Earlier 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
So yeah in the video, traveling salesman should not have been included in NP