Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

2 votes

Simple example of exponential gap between monotone and non-monotone circuits

AFAIU XOR-SAT and perfect matching are simple to understand examples that have polynomial circuit and super polynomial lower bound for monotone circuits.
Dudi Frid's user avatar
  • 201

Top 50 recent answers are included