I'm a high school student, and my question may be trivial, A lucky guesser = a verifier , but what's the benefit of that, a lucky guesser needs some algorithm himself to guess the solution correctly, because it cannot go through all the possible ways in the polynomial time, as it's said that lucky guesser can't make a mistake and will be straightforward with the solution. So, what is the verifier for ? It's more like we can store the lucky guesser's algorithm and just run and conditional check within much less time, that yields 1 or 0 depending on if the solution follows the path of the lucky solver's solution ?
the guesser can actually go through all solutions in polynomial time if he has an algorithm to solve np problem in polynomial time because if he could find an order such that he moved to guess the next solution depending on the answer of the first solution being 0 or 1 and at last end at the first solution he verified and we can conclude that he can definitely find such order to verify the solutions because I have just reduced your question to the traveling salesmen problem which is an np-complete problem and the verifier has an algorithm to solve np problems from which he can verify all solutions in polynomial time
1:41 if that were true than I think NP would contain undecidable problems, since you only care about the fastest branch. The definition I know of is that we look at the worst case, even the branches that reject.
A naive question: If a problem in NP complexity class can be solved in polynomial time by a super lucky series of guesses' pathway, does it not mean that there exists a way to solve the problem in polynomial time, however unlikely it may be? And if so, do all NP problems actually equal P? Of course I know that there is a serious flaw in my reasoning, because we do not know if P equals NP. But I do not know what I'm missing. :-( It will be great if someone can clarify this issue.
we only consider worst case scenarios, basing an algorithm run time on luck doesnt amount to anything usefull, because in theory you can always find a solution with a single guess if you are very lucky, thats not the point of an algorithm
To add to your question - NP complete problems are solved using heuristics if no exact procedure is available.. In other words, devise rules to eliminate any paths which will not lead to a solution. As the problem size grows, the curse of dimensionality makes it extremely difficult to find a solution in a reasonable amount of time. Using relaxation methods may amount to "guessing" which will lead to a quick solution; however the solution may not be optimal.
![Gunna - HIM ALL ALONG [Official Visualizer]](http://i.ytimg.com/vi/HiCxoDeo0hc/mqdefault.jpg)
So, the reason I used Mettaton to depict a checker is because he has a checker pattern...and...so...I'll show myself out.
My favorite is the depiction of the Oracle… sad she didn't appear in this video haha Congratulations for the awesome video.
1:37 can we just appreciate how beautiful this looks
You deserve more subs.I love your videos. You made me like Computer Science again.
I'm a high school student, and my question may be trivial,
A lucky guesser = a verifier , but what's the benefit of that, a lucky guesser needs some algorithm himself to guess the solution correctly, because it cannot go through all the possible ways in the polynomial time, as it's said that lucky guesser can't make a mistake and will be straightforward with the solution. So, what is the verifier for ? It's more like we can store the lucky guesser's algorithm and just run and conditional check within much less time, that yields 1 or 0 depending on if the solution follows the path of the lucky solver's solution ?
the guesser can actually go through all solutions in polynomial time if he has an algorithm to solve np problem in polynomial time because if he could find an order such that he moved to guess the next solution depending on the answer of the first solution being 0 or 1 and at last end at the first solution he verified and we can conclude that he can definitely find such order to verify the solutions because I have just reduced your question to the traveling salesmen problem which is an np-complete problem and the verifier has an algorithm to solve np problems from which he can verify all solutions in polynomial time
I love the pictures you use; a cultured gentleman
awesome!
btw, the more videos about theoretical computer science you poop out before jan 25th the more I love you. ;)
this channel is GOLD
Joe sent me! I'm gonna love this channel!
Nice video as always! Looking forward to an awesome explanation for class IP (and AM) too :)
I love this channel!!!!
thank you. keep doing videos please
Brilliant channel, wish you could get the subs you deserve! Keep it up
I hope some day I'll truly find my own luck
This is kind of an awesome explanation!
what about sublogarithmic time and space? :((
I have my complexity theory exam on the 24th..
how'd it go?
these videos are so good
1:41 if that were true than I think NP would contain undecidable problems, since you only care about the fastest branch.
The definition I know of is that we look at the worst case, even the branches that reject.
A naive question:
If a problem in NP complexity class can be solved in polynomial time by a super lucky series of guesses' pathway, does it not mean that there exists a way to solve the problem in polynomial time, however unlikely it may be? And if so, do all NP problems actually equal P?
Of course I know that there is a serious flaw in my reasoning, because we do not know if P equals NP. But I do not know what I'm missing. :-( It will be great if someone can clarify this issue.
we only consider worst case scenarios, basing an algorithm run time on luck doesnt amount to anything usefull, because in theory you can always find a solution with a single guess if you are very lucky, thats not the point of an algorithm
To add to your question - NP complete problems are solved using heuristics if no exact procedure is available.. In other words, devise rules to eliminate any paths which will not lead to a solution. As the problem size grows, the curse of dimensionality makes it extremely difficult to find a solution in a reasonable amount of time. Using relaxation methods may amount to "guessing" which will lead to a quick solution; however the solution may not be optimal.
Why am i unable to get this concepts 😥😥
The number of choices the NP guesser has to guess from must also be polynomial, otherwise, an NP decider can decide EXPTIME
Even more annoying, the computer scientists can't even separate BPP and NEXP.
Durant la nuit je performe si sa m'tante
Tout comme un petit savant
En sachant que mon sommeil se perfore
Toujours à 6h30