0:20 - 32:10 classification of problems (P, NP, NP-complete, EXP, R, undecidable problems => e.g. "halting problem") 32:10 - 45:20 k-SAT problem (2-SAT is polynomial, 3-SAT is NP complete, all k-SAT for k > 3 can be reduced to 3-SAT) 45:20 - 47:12 emphasis on reduction technique
Its really a meta/self referential issue at some point. Given a really hard problem, decided if it's solvable before you solve it. Doesn't really make sense.
the number of variables in the logical expression does not matter? (i.e., if there is an x sub 5 instead of just up to x sub 4 as in the example here).
I don't understand when he was discussing about that problem on job interview. Was he really trying to say that if you get a problem reduced to an NP-Complete problem try other reductions to reduce it to a P problem because that would be impossible given P is not equal to NP
If you're talking about in the beginning of the video, the halting problem, he says its okay to laugh because you can mathematically (logically, really) that there is no algorithm to solve the halting problem. If someone asks you to solve it and says there is a solution, ask them what it is, because in order for them to have solved it, they would have to literally break the laws of logic. As far as reductions go, if you get a problem you cant find a polynomial time algorithm for, try reducing it to an NP complete problem (in polynomial time). If you can do that, you can goto your employer and tell them something along the lines of "I cant solve it, but no one can, and I can prove it". If your employer argues with you and provides a solution, run off with it and get that sweet million dollar prize for proving P=NP. Also, most importantly of all, as of 2016, no one knows whether P=NP or not. People *think* P
This coin-flipping analogy is not helpful. Isn't it the case that if I get "lucky" I can find a winning strategy in chess? The general solution to chess is in R, so there is a solution, therefore, successive lucky coin flips will yield the correct solution. Why do they keep saying it requires some "magical machine"?
Because the "magical machine" would need to guarantee that each "coin flip" lands on the right face which is theoretically impossible because the face it lands on is probabilistic. It's like saying " what are the odds you *always* randomly pick the optimal move in chess" which, for practical purposes, are essentially 0.
He really should have plainly said to this poor student that you can tell if special programs will ever terminate but it's impossible to solve the halting problem for every program.
I do not understand what does it mean that "The exponential time problem will not solve before the world ends." Is there any proof for this sentence? It doesn't sense to me. Can anybody help me?
It's talking about the practicality of the solution. Even something as simple as factoring a 1024 bit number using long division is time consuming. When you plug in number you get running times in billions of years.
basically in the real world you don't have infinite computation power or infinite time. Everything is limited. And so a good indicator of scalability is the running time complexity.
I don't think it is accurate to put the Halting Problem on a line for easy/hard problems as it is impossible to solve by any algorithm. Not a good teaching technique.
0:20 - 32:10 classification of problems (P, NP, NP-complete, EXP, R, undecidable problems => e.g. "halting problem")
32:10 - 45:20 k-SAT problem (2-SAT is polynomial, 3-SAT is NP complete, all k-SAT for k > 3 can be reduced to 3-SAT)
45:20 - 47:12 emphasis on reduction technique
19:13 Victor speaks the truth
Why they give Victor the tiny chalk?
he keeps breaking them
Its really a meta/self referential issue at some point. Given a really hard problem, decided if it's solvable before you solve it. Doesn't really make sense.
the number of variables in the logical expression does not matter? (i.e., if there is an x sub 5 instead of just up to x sub 4 as in the example here).
I don't understand when he was discussing about that problem on job interview. Was he really trying to say that if you get a problem reduced to an NP-Complete problem try other reductions to reduce it to a P problem because that would be impossible given P is not equal to NP
If you're talking about in the beginning of the video, the halting problem, he says its okay to laugh because you can mathematically (logically, really) that there is no algorithm to solve the halting problem. If someone asks you to solve it and says there is a solution, ask them what it is, because in order for them to have solved it, they would have to literally break the laws of logic.
As far as reductions go, if you get a problem you cant find a polynomial time algorithm for, try reducing it to an NP complete problem (in polynomial time). If you can do that, you can goto your employer and tell them something along the lines of "I cant solve it, but no one can, and I can prove it". If your employer argues with you and provides a solution, run off with it and get that sweet million dollar prize for proving P=NP.
Also, most importantly of all, as of 2016, no one knows whether P=NP or not. People *think* P
what does his tshit means?
This coin-flipping analogy is not helpful. Isn't it the case that if I get "lucky" I can find a winning strategy in chess? The general solution to chess is in R, so there is a solution, therefore, successive lucky coin flips will yield the correct solution. Why do they keep saying it requires some "magical machine"?
Because the "magical machine" would need to guarantee that each "coin flip" lands on the right face which is theoretically impossible because the face it lands on is probabilistic. It's like saying " what are the odds you *always* randomly pick the optimal move in chess" which, for practical purposes, are essentially 0.
Ned's declassified school survival guide
He really should have plainly said to this poor student that you can tell if special programs will ever terminate but it's impossible to solve the halting problem for every program.
She's not that poor. Ive had worse lectures. I would love to have this guy as a teacher at my school.
hahahah, love the shirt!
The guys wearing 1337 shirt 😮
I like it when he goes "YO..."
He is handsome
I do not understand what does it mean that "The exponential time problem will not solve before the world ends." Is there any proof for this sentence? It doesn't sense to me. Can anybody help me?
A solution to a problem that is of exponential complexity has such a bad scalability factor that you might as well disregard that solution altogether.
It's talking about the practicality of the solution. Even something as simple as factoring a 1024 bit number using long division is time consuming. When you plug in number you get running times in billions of years.
basically in the real world you don't have infinite computation power or infinite time. Everything is limited. And so a good indicator of scalability is the running time complexity.
I want that tshirt
I don't think it is accurate to put the Halting Problem on a line for easy/hard problems as it is impossible to solve by any algorithm. Not a good teaching technique.
I would say impossible is pretty hard. The hardest, even.
I am intimidated to read the proof. but maybe one day a quantum algorithm computer will solve the halting problem. never say never right
Its technically possible to solve in infinite time so its fair to include it imo
@@mohamednofal5256 yeah no.
Poor explanation