วีดีโอ

Now, if |x| = n, how can Alice send x to Bob using log(n) bits??

what if we have 3 literals in each of the 3 clause, do we still assign a single buffer too?

Where is the algorithm soloution?

Thank you very much.

10:51 Can you please tell why did you take a triangle as the mixed strategy simplex of the first player? Like can't we take a 1x1x1 cube where the strategy probabilities at any point within it would be its coordinates? The triangle approach doesn't seem so obvious

Should it not be strict subset at 0:40?

After normalization of V, why didn't the equation y4+y5=1/V exit?

Why does evaluating the formula require "some space" c. Why can't we say c = n?

that means that points (2, 1) and (4, 5) are also Nash Equilibrium because 3 is played with probability 0, right?

Thanks for these great lectures. You videos are very easy to understand and follow. Unfortunately in this video I got lost as to why we need n/3 bits of zeros in middle. We could just work with 1 bit of zero. And also, O(k) bits includes all the k times that the tape head leaves the cell in the entire running of TM for palindromes. Then why are we multiplying it with n/3 in the end?

I definitely prefer proof 1, it's a nice elegant counting argument, love a good bit of combinatorics. While also valid, the construction in proof 2 feels more contrived, the altering of the original graph obscures the argument a little.

Thank You for the Great videos. I have a doubt in this video. You said that after the construction of φ, we can put value of x and leave out t, and if the SAT gives a satisfying assignment, that means a t exist which satisfies φ. Connecting it to one of your starting videos where you mentioned that when constructing TM for taking sum of two numbers, we can represent each bit of numbers with duplicates and the plus sign with 10. So, what if, the satisfying assignment that t gives doesn't correspond to any useful info of the certificate? like in case of sum of two nos. example, the t turns out to be 100110101.... or something, which the TM won't recognize cuz it was expecting duplicates and a 10 in between for sum. I hope I am clear enough in my question. It would be great if you could clear my doubt soon.

this Problem is truly a fascinating product of the human imagination, i'm obsessed with it, and yes your channel is amazing

"There's a subsequence of such triangles such that the three corners all converge to the same point z" may not be true and you don't need it, right? You only need there's a subsequence of red points converging to z, a subsequence of blue points converging to z and a subsequence of green points converging to z. But these three subsequences may come from different triangles.

If you didn’t consider 324/3244 then it’s all in a mess

It’s hard after simple

Thankyou.

Thankyou. I’ve been desiring information on this. Greatly appreciated

From partial reductions of the napsack problem to combinations of 2 items to sniff out more item variants of the problem with blocks in some parts of the bag as to find clues for your particular napsack problem

Thank you !!!!!

Lf is basically how to define a set, for which the output is "yes".

Sire, any book recommendation to along this playlist ?

Wouldn't a set of non-result altering transformations which result in True be a verifiable certificate for the Tautology problem? Thanks for the well articulated video.

Who is here in August, 2024. I am.

can you pls proved the pdfs of your notes? they would be really helpful for revising the concepts

thank you very much... this was really helpful :) would be great if you could provide the pdfs of your handwritten notes

The first proof seems to be easier to come up with

Hello @compscilessons Great work you are doing on this channel. I have a favour to ask of you. I have a paper on computational complexity, more specifically on SAT solving and would like a peer review. Unfortunately, I am unaffiliated with any institutions. Can you give me an endorsement on the preprint server arXiv so that I can make a submission or provide an email address where I can share my paper with you? Any assistance on this is appreciated. Thanks.

Really helpful thanks!

Thank you

Why is the g in the definition of a reduction taking in both of x and y?

Very clear explanation - Thanks! One Question: What would we do, if we insist, that the numbers given as instance for the SUBST SUM problem are different to each other?

No other video explains the pricing method on weighted vertex covers as well as yours, thank you so much, great video

You are genuinely awesome.

you are single handedly saving my ass. may your soul be blessed

Anyway, thank you. This video helped me a lot 🎉

Can you please do the colonel Blotto game

you did good job but my stoopid self could not understand it.

Why is that true? What about a clause of the form: x and ~y? It is not satistied when x and y are true and not satisfied when x and y are false.

you really don't explain things well

This was a very helpful explanation. The part after 13:00 was especially helpful explaining the purpose of the additional rows

Your channel is the best theoretical CS channel I've seen, fantastic job! thank you!

when you wrote down that proof idea at 2:30 my mouth started watering lets see where this goes

this module is so so good

Thank You!!

Thanks!

thank you so so so so much!!! you explain everything so clearly!!!!

i am going to now define the concept of mebeingfkingright. this foundational principle, now called mebeingfkingright, will be proven in the following way. i propose a machine, called the RightMachine that lays out a sequence of adjacent symbols. in each symbol is encoded the final position of the symbol to the left of itself or non at all. the machine beingfkingright at r0 and ends at r-finished. any sequence that this machine can lay down is said to be mebeingfkingright. therefore mebeingfkingright is any seqquence of symbols of mebeingfkingright that the RightMachine can process i.e. can go from r0-r-finish. tada the same level of proof as computability in this turing complete nonsense. the entire field of computer science folks.. like seriously without information theory and linguistics, computer science would just be a joke based on the inane crackpot nonsense of two guys during ww2.

Sir, you are doing God's work

Teacher, time 1:01, you write a f:{0,1}*: What does asterisk (*) mean?