![Computer Science Theory Explained](/img/default-banner.jpg)
- 116
- 341 115
Computer Science Theory Explained
United Kingdom
Приєднався 24 чер 2020
Binary vs. Unary Number Encodings and Strong NP-completeness
Textbooks:
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.
Lecture slides by K. Wayne accompanying the latter textbook:
www.cs.princeton.edu/~wayne/kleinberg-tardos/
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.
Lecture slides by K. Wayne accompanying the latter textbook:
www.cs.princeton.edu/~wayne/kleinberg-tardos/
Переглядів: 1 202
Відео
The Lemke-Howson Algorithm - Complementary Pivoting
Переглядів 3,4 тис.2 роки тому
The Lemke-Howson Algorithm - Complementary Pivoting
The Lemke-Howson Algorithm - Best Response Polytopes
Переглядів 2,9 тис.2 роки тому
The Lemke-Howson Algorithm - Best Response Polytopes
The Lemke-Howson Algorithm - Best Response Diagrams
Переглядів 4 тис.2 роки тому
The Lemke-Howson Algorithm - Best Response Diagrams
Colorability of Planar Graphs
Переглядів 1,4 тис.2 роки тому
Textbooks: Computational Complexity: A Modern Approach by S. Arora and B. Barak. Algorithm Design by J. Kleinberg and E. Tardos. Lecture slides by K. Wayne accompanying the latter textbook: www.cs.princeton.edu/~wayne/kleinberg-tardos/
Nash's Theorem
Переглядів 2,4 тис.2 роки тому
John Nash's PhD Thesis: library.princeton.edu/special-collections/sites/default/files/Non-Cooperative_Games_Nash.pdf
Two-Player Zero-Sum - a Second Example
Переглядів 1,2 тис.2 роки тому
Two-Player Zero-Sum - a Second Example
Existence and Computation of Nash Equilibria in Two-Player Zero-Sum Games
Переглядів 1,7 тис.2 роки тому
Existence and Computation of Nash Equilibria in Two-Player Zero-Sum Games
A Brief Linear Programming Refresher
Переглядів 1,1 тис.2 роки тому
A Brief Linear Programming Refresher
The Poisened Drink and the Mixed Nash Equilibrium
Переглядів 1,1 тис.2 роки тому
The Poisened Drink and the Mixed Nash Equilibrium
The Battle of the Sexes and Burning Money
Переглядів 1,4 тис.2 роки тому
The Battle of the Sexes and Burning Money
Pure Nash Equilibrium - a Further Example
Переглядів 8102 роки тому
Pure Nash Equilibrium - a Further Example
The Iterated Elimination of Dominated Strategies
Переглядів 1,9 тис.2 роки тому
The Iterated Elimination of Dominated Strategies
Dominating Strategies in the Prisoner's Dilemma
Переглядів 1,3 тис.2 роки тому
Dominating Strategies in the Prisoner's Dilemma
The "Tragedy" in the Tragedy of the Commons
Переглядів 1,6 тис.2 роки тому
The "Tragedy" in the Tragedy of the Commons
Algorithmic Game Theory - Introduction
Переглядів 6 тис.2 роки тому
Algorithmic Game Theory - Introduction
Another Dynamic Program for the Knapsack Problem
Переглядів 7093 роки тому
Another Dynamic Program for the Knapsack Problem
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?
O.K., the solution is given at the end!
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
wow. beautiful
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?
The * is referred to as the Kleene star. {0,1}* is the set of all bitstrings of arbitrary (but finite) length. This includes the empty string, i.e., the string that has length 0.
Yup im bout to fail my exam lol
Was the question "What is Computation?" ever directly answered? Is a computation one run of a Turing machine from q_start to q_end? But even that doesn't answer the question, it only provides an example of a computation which is different than defining it.
Thank you!
Can u exaplian why (0,0,1) true but (0,1,0) false , plz i need u ?
this is just an example for an arbitrary formula, it's not the case that φ(0,0,1) = true and φ(0,1,0) = false in general
oh wow, thanks! big fan of this thesis! it does seem like we'll get computer simulations that you can't distinguish from reality one day!
Amazing work!
If K = 3 or generally > 2, can you still find a solution in polynomial time?
thank you ,do you have the code of the The List Scheduling Algorithm? if you have,can you share with me please.
This course is pure gold. Many thanks for your time and effort man
Really nice course, I watched it with interest and joy.
really well explained, thank you!
Hervorragend!
thanks, saving my grade fr <3
It’s been enjoyable journey into the Complexity theory. Thank you Matthias
best video out there for planar and graph color
simply amazing, your explanations are phenomenal
Amazing tutorial! Explained the concepts behind LH algorithms brilliantly
life saver
Why can't x1 and ~x2 both be green? Or red?
in this case the problem is that Xi and ~Xi have the same color, as this would not be consistent. In the case of a 3SAT problem formula, we must have at least one of the literals have the true value, therefore, I believe that nothing prevents it from having two true values as long as they are not opposite literals. My english is very bad, sorry
Could you please explain why is there is a condition on T(n) >= n for all n in N in the second case for k-tape example?
Because the machine should be able to read the whole input.