Strict-majority circuits -- definitions

The raw construction specializes the unary threshold compiler to the smallest integer strictly larger than half the input count. Primary input i is used directly as referenced wire i.

def Complexity.CircuitCode.strictMajorityThreshold (inputCount : ℕ) : ℕ

Smallest integer count constituting a strict majority.

Equations

• Complexity.CircuitCode.strictMajorityThreshold inputCount = inputCount / 2 + 1

def Complexity.CircuitCode.strictMajorityRawCircuit (inputCount : ℕ) : RawCircuit

Raw fan-in-two circuit testing whether its primary inputs contain a strict majority of true bits.

Equations

• One or more equations did not get rendered due to their size.