17. Space Complexity, PSPACE, Savitch's Theorem

TL;DR

We explore space complexity and discuss the TQBF problem, a language of true quantified boolean formulas, which can be solved in NP space.

Transcript

so we've been talking about p and np and the time complexity classes and today we're going to shift gear we're going to talk about uh space complexity or memory complexity as uh space complexity is what complexity theorists uh usually refer refer to it as um and um you know time and space are the two basic most basic measures of complexity that uh ... Read More

Key Insights

• 👾 Space complexity is another important measure of complexity, alongside time complexity.
• 🏛️ Space complexity classes are defined similarly to time complexity classes.
• 👾 Language classes like P and NP can also be classified based on their space complexity.

Questions & Answers

Q: How is space complexity defined for Turing machines?

Space complexity for Turing machines is measured by counting the number of cells visited on the tape during the computation. The total number of cells visited is considered, with re-visiting the same cell multiple times only counting once.

Q: Can non-deterministic Turing machines have a specific space complexity?

Yes, non-deterministic Turing machines can have a space complexity. For a non-deterministic machine, the space used is calculated by considering the highest number of tape cells used on any branch of the computation.

Q: How are space complexity classes defined for Turing machines?

Space complexity classes are defined similarly to time complexity classes. For example, polynomial space (PSPACE) represents all languages decidable by a deterministic Turing machine using polynomial space. Non-deterministic polynomial space (NPSPACE) represents languages decidable by a non-deterministic Turing machine using polynomial space.

Q: Can multi-tape Turing machines also have space complexity?

Yes, space complexity can be defined for multi-tape Turing machines. It considers the sum of all tape cells used across all tapes. However, the space complexity classes for multi-tape Turing machines are the same as for single-tape machines.

Summary & Key Takeaways

• Space complexity is an important measure of complexity in addition to time complexity.

• The space complexity classes, including polynomial space and non-deterministic polynomial space, are defined and compared to the time complexity classes.

• The TQBF problem involves determining whether a ladder of strings can be formed within a given language and is solvable in NP space.