Theory of computation - Advanced Computation Topics

Computability and Computational Complexity Theory Introduction Computability theory and computational complexity theory answer two related but distinct questions about problems in computer science. Computability theory asks: Can this problem be solved at all by a computer? Computational complexity theory asks a more practical question: If a problem can be solved, how efficiently can it be solved? Together, these fields form the theoretical foundation for understanding the fundamental capabilities and limitations of computation. Part 1: Computability Theory What is Computability Theory? Computability theory investigates which problems can be solved by a computer and which cannot. It doesn't matter how long the computer runs—we only care about whether a solution exists at all. This field uses formal models of computation, primarily the Turing machine, as a universal standard for what "computable" means. The core insight of computability theory is that not all problems can be solved by computers, no matter how much time or memory we allow. Some problems are fundamentally undecidable. The Halting Problem: An Undecidable Problem One of the most famous results in computer science is the halting problem impossibility result. The halting problem asks: given any Turing machine and an input, can we determine whether that machine will eventually halt (stop running) or run forever? Intuitively, this seems like it should be solvable—after all, we could just simulate the machine and see what happens. However, the halting problem is undecidable: no Turing machine exists that can correctly determine, for every possible machine-input pair, whether that machine will halt. Why is the halting problem important? It demonstrates that there exist well-defined computational questions that no algorithm can answer, no matter how clever. This places a fundamental limit on what computers can do. Rice's Theorem: A General Impossibility Result The halting problem is just one example of an undecidable problem. Rice's theorem provides a much more general impossibility result. Rice's theorem states that every non-trivial property of the partial function computed by a Turing machine is undecidable. In simpler terms: if you want to ask any interesting yes-or-no question about what a program does (rather than how it's written), and that question isn't trivially true or false for all programs, then no algorithm can answer it. For example: "Does this program terminate on all inputs?" (undecidable) "Does this program ever print the letter 'A'?" (undecidable) "Does this program compute a total function?" (undecidable) What makes these "non-trivial"? A property is non-trivial if it's true for some Turing machines but false for others. Rice's theorem tells us these problems cannot be solved algorithmically. <extrainfo> Connection to Recursion Theory Computability theory is closely related to recursion theory, which studies models of computation and their relationships. While this provides important theoretical context for understanding computability, it is primarily background knowledge rather than core exam material. </extrainfo> Part 2: Computational Complexity Theory What is Computational Complexity Theory? While computability theory asks "can we solve this?", computational complexity theory asks "how efficiently can we solve this?" Computational complexity theory examines not only whether a problem can be solved, but also the resources (time and memory) required to solve it. This distinction is crucial in practice. A problem might be solvable in theory but require billions of years to compute—hardly useful in practice. Complexity theory helps us understand which problems have efficient solutions and which remain intractable despite being solvable. Time Complexity: Measuring Computational Steps Time complexity measures the number of basic computational steps required to solve a problem as a function of the input size. We denote time complexity as $T(n)$, where $n$ represents the size of the input. For example: Checking if a number is in a sorted list of $n$ items using binary search takes roughly $T(n) = \log2(n)$ comparisons Checking if a number is in an unsorted list takes roughly $T(n) = n$ comparisons Sorting a list of $n$ items using a good algorithm like merge sort takes roughly $T(n) = n \log n$ comparisons Notice that we count the number of steps as a function of input size—the larger the input, the more steps needed. Space Complexity: Measuring Memory Usage Space complexity measures the amount of memory required to solve a problem as a function of the input size. We denote space complexity as $S(n)$, where $n$ is again the input size. For example: An algorithm that uses a single counter variable uses $S(n) = O(1)$ space (constant, doesn't depend on input size) An algorithm that stores a copy of the input in memory uses $S(n) = O(n)$ space Some algorithms may use even more memory than the input size Understanding space complexity matters when working with limited memory environments, such as embedded systems or massive datasets. Big O Notation: Asymptotic Analysis When we say an algorithm has time complexity $T(n) = n \log n$, we're giving a specific formula. However, in practice, we often use Big O notation to describe complexity in a more flexible way. Big O notation, written as $O(f(n))$, describes the asymptotic upper bound of a function. It tells us how a function grows as $n$ becomes very large, while ignoring constant factors and lower-order terms. For instance: An algorithm with 5 steps takes $T(n) = 5$, but we write this as $O(1)$ (constant time) An algorithm with $100n + 50$ steps takes $T(n) = 100n + 50$, but we write this as $O(n)$ (linear time) An algorithm with $2n^2 + n + 10$ steps is $O(n^2)$ (quadratic time) Why ignore constants? Because constant factors depend on the specific computer, programming language, and implementation details. The Big O notation focuses on what matters: how the algorithm scales with larger inputs. An $O(n)$ algorithm will always be faster than an $O(n^2)$ algorithm for sufficiently large $n$, regardless of the constant factors. Common complexity classes you should know, from fastest to slowest growth: $$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$ The P vs NP Problem: The Central Question in Complexity Theory The P vs NP problem is arguably the most important open question in computer science. To understand it, we need to define two complexity classes: P (Polynomial time): Problems that can be solved in polynomial time. If an input has size $n$, we can find the solution in roughly $n^k$ steps for some constant $k$. NP (Nondeterministic Polynomial time): Problems whose solutions can be verified in polynomial time. If someone gives you a proposed solution, you can check whether it's correct quickly. The central question: Is P = NP? In other words, if we can verify solutions quickly, can we also find solutions quickly? This is surprisingly hard to answer! Here are some examples that illustrate the difference: Multiplication: Given two numbers, compute their product (in P—easy to solve). Conversely, given a product, find the factors (factoring, in NP—easy to verify, but hard to find) Satisfiability: Given a logical formula, is there an assignment of variables that makes it true? (in NP—easy to verify a solution, but seems hard to find one) Why does this matter? If P = NP, then every problem we can verify quickly can also be solved quickly. This would revolutionize cryptography, optimization, and many other fields. If P ≠ NP, then some problems are fundamentally harder to solve than to verify. <extrainfo> The P vs NP problem is one of the seven Millennium Prize Problems defined by the Clay Mathematics Institute in 2000. A correct solution earns a $1 million prize, reflecting how fundamental and difficult this question is. </extrainfo> The diagram above shows the hierarchy of complexity classes. Notice how P sits inside NP, and both sit inside larger classes like PSPACE. If P = NP, the inner circles would collapse into the same space; currently, we don't know.