Thanks to my supporters Yuri (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Thank you so much for your amazing explanation. I still have a question: The verifier has to be deterministic, as far as I've understood it. If we verify a language L in polynomial time we can only say that the L is in NP. Why doesn't this prove that L is in P, when we already use a deterministic algorithm to verify L?
I wanted to share the solution of my research on this (sorry that it’s coming so late, I forgot about this comment): The verifier checks every guessed certificate and to guess a certificate you need a non-deterministic Turing machine. Hence, you can only verify, whether the problem/language is in NP or not.
hello, so, if I understood correctly: if k is the number of nodes in a subset of nodes of the G graph, then verifying if a certain subset of k nodes of G is a clique can be done in O(binomial coefficient of k on 2), and is this complexity considered polynomial?
Thanks to my supporters Yuri (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Thank you! great explanation 👏👏
Keep up the good work!
Thanks!
Thank you so much for your amazing explanation.
I still have a question: The verifier has to be deterministic, as far as I've understood it. If we verify a language L in polynomial time we can only say that the L is in NP. Why doesn't this prove that L is in P, when we already use a deterministic algorithm to verify L?
I wanted to share the solution of my research on this (sorry that it’s coming so late, I forgot about this comment): The verifier checks every guessed certificate and to guess a certificate you need a non-deterministic Turing machine. Hence, you can only verify, whether the problem/language is in NP or not.
hello, so, if I understood correctly: if k is the number of nodes in a subset of nodes of the G graph, then verifying if a certain subset of k nodes of G is a clique can be done in O(binomial coefficient of k on 2), and is this complexity considered polynomial?
Late response, but in case it is useful to anyone else later on:
Yes. C(k,2) essentially equals [k(k-1)]/2. Which is polynomial. O(k^2)