P/poly

Definition

The class p/poly consists of decision problems that can be solved by polynomial-size families of Boolean circuits. This class is important in understanding the limits of efficient computation because it captures problems that can be computed non-uniformly, allowing for different circuits for different input sizes. p/poly helps to bridge the gap between circuit complexity and Turing machine computations, highlighting the relationship between computational resources and problem-solving capabilities.

5 Must Know Facts For Your Next Test

1. p/poly contains all languages that can be decided by polynomial-size Boolean circuits, making it a crucial class in circuit complexity.
2. It includes problems that may not be efficiently solvable by uniform algorithms, highlighting the differences between uniform and non-uniform computations.
3. If a language is in p/poly, it implies that there exists a family of circuits, one for each input length, such that the size of these circuits is bounded by a polynomial function.
4. p/poly is often used in discussions regarding the relationships between complexity classes, especially concerning NP and co-NP problems.
5. A fundamental result is that if NP is contained in p/poly, it would imply some surprising consequences regarding the collapse of complexity classes.

Review Questions

• How does p/poly relate to the concept of non-uniform computation and why is this significant?
  • p/poly relates to non-uniform computation by allowing different Boolean circuits to be used for inputs of varying sizes, rather than requiring a single algorithm to handle all inputs uniformly. This distinction is significant because it demonstrates how certain problems may be efficiently solved with tailored resources, yet remain difficult or unsolvable within uniform frameworks. Understanding this helps researchers evaluate the inherent limitations of computational models and emphasizes the importance of circuit families in complexity theory.
• Discuss how p/poly serves as a bridge between circuit complexity and Turing machine complexity, especially regarding decision problems.
  • p/poly serves as a bridge between circuit complexity and Turing machine complexity by showing how polynomial-size circuit families can solve decision problems efficiently. While Turing machines represent a uniform approach to computation, p/poly illustrates how certain languages can be computed non-uniformly with varying resources based on input size. This connection allows for insights into how different computational models interact and helps inform our understanding of which problems are efficiently solvable under various definitions of computational power.
• Evaluate the implications if NP were found to be contained within p/poly, particularly on the broader landscape of computational complexity.
  • If NP were found to be contained within p/poly, it would imply that every problem in NP could be solved using polynomial-size circuits. This would lead to significant consequences in computational complexity theory, such as suggesting that P = NP would not hold true under common assumptions. Additionally, it could trigger a collapse of many known complexity class separations, fundamentally altering our understanding of algorithmic efficiency and the nature of hard problems. Such an outcome would prompt a reevaluation of many foundational theories in computer science.

Related terms

Boolean Circuits: A model of computation that uses logical gates arranged in a directed acyclic graph to compute functions, where each gate represents a logical operation on its inputs.

Circuit Complexity: A measure of the computational complexity of Boolean functions based on the size and depth of the circuits required to compute them.

Non-uniformity: The property of a computational model that allows for different resources or structures (like circuits) to be used for inputs of different sizes, as opposed to uniform models that require a single resource for all input sizes.