Videos

CSDM - On The Complexity of Circuit Satisfiability

Presenter
October 12, 2009
Keywords:
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
We present a gap theorem regarding the complexity of the circuit satisfiability problem.We prove that the success probability of deciding Circuit Satisfiability for deterministiccircuits with n variables and size m is either 2−n or 2−o(n) when restricted to probabilisticcircuit families {Cn,m} where the size of Cn,m is bounded by 2o(n)poly(m).
Supplementary Materials