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.
Keep up the good work!
Thanks!
Thank you! great explanation 👏👏
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)