Here we introduce the notion of "logarithmic space", which is understanding what problems can be solved with a "very small" amount of space. We define what a Turing Machine needs to do in order to achieve that, as well as give some example problems that are in deterministic log space, and nondeterministic log space.
What is space in complexity theory? It is the maximum amount of cells used on a Turing Machine that runs on inputs of size n. See • What is Space? (for co... for more details.
Timeline:
0:00 - Intro
2:30 - Model for Small Space
7:30 - Definition of Log Space and Nondet Log Space
8:30 - All regular languages are in L
15:05 - {0^n 1^n} is in L
18:25 - PATH vs DPATH, DPATH in NL
Easy Theory Website: www.easytheory.org
Become a member: / @easytheory
Donation (appears on streams): streamlabs.com/easytheory1/tip
Paypal: paypal.me/easytheory
Patreon: / easytheory
Discord: / discord
KZread Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: teespring.com/language-hierar...
Pumping Lemma Apparel: teespring.com/pumping-lemma-f...
If you like this content, please consider subscribing to my channel: / @easytheory
▶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.