Formal Computer Science / Optimization

Kenton Labs / Optimization

Circuit minimization

A working circuit proves an upper bound. Minimality additionally requires ruling out every smaller circuit in the stated gate model.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Gate basis
The allowed primitive Boolean operations; this family uses two-input NAND.
Truth-table signature
The complete output function over the four input rows 00, 01, 10, 11.
Cost model
Gate count, with acyclic wiring, reusable signals, and unrestricted fan-out.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Evaluate the witness circuit in topological signal order.
  2. Compare its complete truth table with the target function.
  3. Enumerate all smaller acyclic circuits, identifying symmetric NAND inputs.
  4. Reject minimality if any smaller circuit implements the target.

Cost and scope

The circuit search grows rapidly with gate count. This family keeps two inputs and at most four witness gates.

A common failure

Gate-count minimality does not imply minimum delay, energy, area, or transistor count.

Explore the mechanics.

Change a local input or follow the steps. The stored result and its scope remain attached to the downloadable record.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-009
Circuit minimizationXOR with a minimum NAND countWitness truth table + complete smaller-circuit search

The problem

Find the fewest two-input NAND gates for XOR(a,b), with acyclic wiring, reusable signals, unrestricted fan-out, no constants, and one gate-output signal.

The checked result

Minimum gates: 4.

The four-gate witness yields the XOR truth table. The checker enumerates every topologically ordered circuit with fewer than four gates, identifying symmetric NAND inputs, and finds none that implements XOR.

Why the checker accepts it

  1. Evaluate the witness circuit in topological signal order.
  2. Compare its complete truth table with the target function.
  3. Enumerate all smaller acyclic circuits, identifying symmetric NAND inputs.
  4. Reject minimality if any smaller circuit implements the target.

Formal specification

{
  "truth_table": 6,
  "row_order": "00, 01, 10, 11; row i is bit i",
  "gate_basis": "two-input NAND; repeated inputs permitted; no constants"
}

Claim and evidence

{
  "claim": {
    "minimum_gates": 4
  },
  "witness": {
    "gates": [
      [
        0,
        1
      ],
      [
        0,
        2
      ],
      [
        1,
        2
      ],
      [
        3,
        4
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 4 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

The circuit search grows rapidly with gate count. This family keeps two inputs and at most four witness gates.

Minimality is relative to this precise gate basis and wiring model. It says nothing about transistor count, delay, power, or other gate libraries.

A boundary to investigate

Gate-count minimality does not imply minimum delay, energy, area, or transistor count. Add independently checked lower bounds and additional gate libraries.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-022 ↘Related KL-FCS-023 ↘
KL-FCS-022
Circuit minimizationNegation from a repeated NAND inputComplete truth table + zero-gate lower bound

The problem

Minimize the gate count for the declared two-input truth-table signature.

The checked result

Minimum gates: 1.

A single NAND gate supplies the target. Neither available input wire has the same signature, so no zero-gate implementation exists.

Why the checker accepts it

  1. Evaluate the witness circuit in topological signal order.
  2. Compare its complete truth table with the target function.
  3. Enumerate all smaller acyclic circuits, identifying symmetric NAND inputs.
  4. Reject minimality if any smaller circuit implements the target.

Formal specification

{
  "truth_table": 3,
  "row_order": "00, 01, 10, 11; row i is bit i",
  "gate_basis": "two-input NAND; repeated inputs allowed; no constants"
}

Claim and evidence

{
  "claim": {
    "minimum_gates": 1
  },
  "witness": {
    "gates": [
      [
        0,
        0
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 1 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

The circuit search grows rapidly with gate count. This family keeps two inputs and at most four witness gates.

The lower bound applies only to the specified two-input NAND basis.

A boundary to investigate

Gate-count minimality does not imply minimum delay, energy, area, or transistor count. Add independently checked lower bounds and additional gate libraries.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-009 ↘Related KL-FCS-023 ↘
KL-FCS-023
Circuit minimizationThe NAND primitive is minimalComplete truth table + zero-gate lower bound

The problem

Minimize the gate count for the declared two-input truth-table signature.

The checked result

Minimum gates: 1.

A single NAND gate supplies the target. Neither available input wire has the same signature, so no zero-gate implementation exists.

Why the checker accepts it

  1. Evaluate the witness circuit in topological signal order.
  2. Compare its complete truth table with the target function.
  3. Enumerate all smaller acyclic circuits, identifying symmetric NAND inputs.
  4. Reject minimality if any smaller circuit implements the target.

Formal specification

{
  "truth_table": 7,
  "row_order": "00, 01, 10, 11; row i is bit i",
  "gate_basis": "two-input NAND; repeated inputs allowed; no constants"
}

Claim and evidence

{
  "claim": {
    "minimum_gates": 1
  },
  "witness": {
    "gates": [
      [
        0,
        1
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 1 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

The circuit search grows rapidly with gate count. This family keeps two inputs and at most four witness gates.

The lower bound applies only to the specified two-input NAND basis.

A boundary to investigate

Gate-count minimality does not imply minimum delay, energy, area, or transistor count. Add independently checked lower bounds and additional gate libraries.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-009 ↘Related KL-FCS-022 ↘

Go further.

Add independently checked lower bounds and additional gate libraries.

Questions to investigate

  1. Gate-count minimality does not imply minimum delay, energy, area, or transistor count.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add independently checked lower bounds and additional gate libraries.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

SchedulingCombinatorial optimizationConstraint satisfaction