The Cook-Levin Theorem FULL PROOF (Boolean Satisfiability is NP-complete)
Here we give the full proof that SAT is NP-complete, which is a general polynomial-time reduction from any problem B in NP. We use the "tableau" proof which encodes the transitions of a nondeterministic poly-time TM.
▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com
▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=LW_37i96htQ
Here we start with a context-free grammar (CFG) for the set of all balanced parentheses, and convert this CFG into Chomsky Normal Form (CNF). The method used is the one here: https://www.youtube.com/watch?v=-SZkkMWHBvQ&ab_channel=EasyTheory.
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Timmy Gy, Josh Hibschman, Patrik Keinonen, Travis Schnider, and Tao Su
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=VqzFpJlcoWY
Here we look at a user's Python code to handle a budget.
Easy Theory Website: https://www.easytheory.org
Discord: https://discord.gg/SD4U3hs
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
...
https://www.youtube.com/watch?v=7WQ8HBzRhpQ
Here we prove the time hierarchy theorem, which says that for any "sufficiently suitable" function t(n), there is a language solvable in O(t(n)) time and not in o(t(n) / log t(n)) time.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=l2aXF0B2E9M
Here we start context-free grammars (CFG) and context-free languages (CFL), which are the languages of CFGs. The idea is to have every rule's right-hand side allowed to have any combination of variables and terminals. We show that every regular grammar is already a context-free grammar, and not necessarily the other way around because we give an example of a CFG for {0^n 1^n : n at least 0}, which is not regular. We then make a CFG for the language of palindromes over {0,1}.
What is a context-free grammar? It is a set of 4 items: a set of "variables," a set of "terminals," a "start variable," and a set of rules. Each rule must involve a single variable on its "left side", and any combination of variables and terminals on its right side.
Timestamps:
0:00 - Intro
0:35 - Grammars (generally)
2:35 - Example grammar that has nonregular language
7:45 - Context-Free Grammar (CFG) definition
11:15 - Example CFG for Palindromes
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=h1OSmLSacNA
Here we show that deterministic context-free languages (DCFLs) are not closed under concatenation. The idea is to have two languages whose concatenation is the complement of {a^n b^n c^n : n at least 0}, which is not a DCFL.
A deterministic context-free language is the language of a deterministic pushdown automaton (DPDA). The essential idea is that a DPDA is equivalent to a PDA, except that there can only be one "choice" of transition from any state on any input, with anything on the stack. See https://www.youtube.com/watch?v=GzR5FiiIogY&ab_channel=EasyTheory for more details.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=qGOw0n9gJR4
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below.
Dolev Abuhazira, Josh Hibschman, Micah Wood, Morgan Jones, Patrik Keinonen, Simone Glinz, Tao Su, Timothy Gorden, unit220, Valentine Eben
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=Xqp6o52lZOM
Here we give a short video on how to return a boolean correctly (this case in Python). Many beginners make this mistake!
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below.
Dolev Abuhazira, Josh Hibschman, Micah Wood, Morgan Jones, Patrik Keinonen, Simone Glinz, Tao Su, Timothy Gorden, unit220, Valentine Eben
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
...
https://www.youtube.com/watch?v=-mEQ_SWc2GE
Original covering arrays video: https://www.youtube.com/watch?v=m1j4OBs1wsY&ab_channel=EasyTheory
arXiv preprint: https://arxiv.org/pdf/2211.01209.pdf
Here we discuss a recent proof of mine of a conjecture in my research area, which has to do with sizes of covering arrays. I first go over what the problem, which is determining the asymptotic sizes (# of rows) of covering arrays of "higher index", which is to say each interaction must appear at least a certain number of times, instead of just once. I give "easy" upper and lower bounds; unlike the prior video's scenario, there is a "gap" between them. Next I give some upper bounds that have been published and are "better", but there is still a small gap. My proof this year is that there is no gap between the "easy" lower bound and the new upper bound I prove, which is logarithmic in the number of columns, and additively linear in the index.
This proof also uses the probabilistic method, but with a new ingredient: the Lambert W function. My proof first uses the Cauchy-Schwarz inequality on the equation coming from the probabilistic method. The C-S inequality relates cross correlations of sums (hard to understand) to self-correlations (easy to understand), but paying a penalty; in other words, sum(a_i * b_i) changes to sum(a_i^2) * sum(b_i^2) * penalty. Then we use simple known upper bounds on the two sums that come out. The final "trick" is to use the Lambert W function, which is the inverse of f(W) = W * e^W. One would have to analyze the equation that comes out, and notice where in the Lambert W function one is; in this case, it is in the negative region. To finish everything off, we use *lower* bounds on W since in this region, W is negative (which translates to *upper* bounds on covering array sizes).
Easy Theory Website: https://www.easytheory.org
Discord: https://discord.gg/SD4U3hs
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
...
https://www.youtube.com/watch?v=D3H8yEuCsSk
Credit: https://cs.stackexchange.com/a/60791
Here we give an involved proof to give strong evidence that there is no "pumping lemma for context-sensitive languages." The idea is that if there is one, then one can show that the "infinity" problem for that model is recognizable, but this is impossible for CSLs because that problem is unrecognizable (as we prove with linear bounded automata).
Timeline:
0:00 - Intro
1:20 - What does a "pumping lemma" mean?
6:45 - If the predicate exists, then Infinity Problem is recognizable
13:43 - Infinity Problem for LBAs is not recognizable
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=nOJlfXGoqEQ