Logarithmic Space in Complexity Theory - Easy Theory

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 https://www.youtube.com/watch?v=yMhQdU5j6ag&t=8s&ab_channel=EasyTheory 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: 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

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=X9R6mvENyQQ