Computability and Complexity

Formalizing the Problem This section establishes quantitative complexity measures for Boolean functions and formally defines depth-2 circuits with bounded fan-in gates. It discusses the challenges in proving lower bounds against circuits with small depth due to limited computational power. Establishing complexity measures We introduce notation and terminology to quantify the complexity of Boolean functions in…

Overcoming Barriers to BPP Lower Bounds The complexity class BPP, consisting of problems solvable in probabilistic polynomial time with bounded error, has proven notoriously difficult to establish lower bounds for. While NP-hardness proofs establish computational intractability assuming P ≠ NP, proving problems are hard for BPP requires defeating the power of randomness and is thus…

The P vs NP Problem and Its Implications The P vs NP problem refers to the open question of whether or not the complexity classes P and NP are equal. The class P contains decision problems that can be solved in polynomial time by a deterministic Turing machine. The class NP contains problems where solutions…

Defining the Complexity Classes BPP and P Probability distributions play a key role in defining randomized computational complexity classes. The class BPP consists of decision problems that can be solved by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. In contrast, P is the class…

Is BPP Closed Under Complement? The complexity class BPP (Bounded-error Probabilistic Polynomial time) contains decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/2 for all instances. A key question is whether BPP is closed under complement – that is, if a problem is in BPP,…

Formalizing Distributed and Parallel Systems Modern computer systems increasingly rely on distributed and parallel architectures to meet the growing demands for performance and scalability. Formal models provide mathematical abstractions that can precisely capture the semantics and behaviors of these complex systems. Leveraging Process Calculi to Model Concurrency Process calculi such as the pi-calculus provide formalisms…

Representing Infinite Sets with Recursion Recursion is a powerful technique in mathematics and computer science that involves defining objects in terms of themselves. This self-referential capability allows recursive definitions to characterize objects that have potentially infinite size or unbounded extent. Two major applications of recursive representations are: (1) specifying infinite sets, and (2) defining computable…

The Promise of Intermediacy The field of computational complexity categorizes mathematical problems based on the resources required to solve them. Problems fall into complexity classes based on the time or space needed by algorithms to find solutions. Two important complexity classes are P and NP. P contains problems that can be solved in polynomial time…

The Power of Oracle Separations Oracle separations are a powerful technique in computational complexity theory for demonstrating differences between complexity classes. An oracle is an external “black box” that algorithms can query to obtain information. By constructing oracles that create differences in the behaviors of algorithms from two complexity classes, oracle separations prove that the…

Exploring the Gap Between Polynomial Time and NP-Completeness The classes P and NP represent fundamental measures of computational complexity. P consists of all decision problems that can be solved in polynomial time by a deterministic Turing machine. NP consists of all decision problems where a “yes” answer can be verified in polynomial time given the…