Formal Computer Science / Optimization

Kenton Labs / Optimization

Constraint satisfaction

Expose both satisfiable assignments and complete impossibility arguments for finite variable domains.

The vocabulary.

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

Constraint
A relation restricting allowed variable assignments.
Graph coloring
Adjacent vertices must receive different colors.
Solution space
Every assignment satisfying all declared constraints.

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. Enumerate one color value for each vertex.
  2. Check every edge’s unequal-color constraint.
  3. Count the complete solution space.
  4. Validate a coloring witness, or require enumeration evidence when no model exists.

Cost and scope

k colors on n vertices produce kⁿ assignments. Color-label permutations can create symmetric solutions.

A common failure

Failing to find a solution is not equivalent to proving there is none.

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-046
Constraint satisfactionA triangle cannot use two colorsComplete assignment space · 8 candidates

The problem

Decide and count color assignments satisfying every graph edge.

The checked result

Satisfiable: no; Solution count: 0.

Every assignment either yields a fully valid coloring or an edge witnessing failure. Counting includes distinct color labels, so symmetric assignments remain separate.

Why the checker accepts it

  1. Enumerate one color value for each vertex.
  2. Check every edge’s unequal-color constraint.
  3. Count the complete solution space.
  4. Validate a coloring witness, or require enumeration evidence when no model exists.

Formal specification

{
  "vertices": 3,
  "edges": [
    [
      0,
      1
    ],
    [
      1,
      2
    ],
    [
      2,
      0
    ]
  ],
  "colors": 2
}

Claim and evidence

{
  "claim": {
    "satisfiable": false,
    "solution_count": 0
  },
  "witness": {
    "method": "exhaustive enumeration"
  }
}

Dataset construction

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

Complexity and limits

k colors on n vertices produce kⁿ assignments. Color-label permutations can create symmetric solutions.

This is a finite coloring instance; the solution count is not reduced by graph or color symmetries.

A boundary to investigate

Failing to find a solution is not equivalent to proving there is none. Add symmetry reduction and checked propagation or conflict explanations.

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-047 ↘Related KL-FCS-048 ↘
KL-FCS-047
Constraint satisfactionA four-cycle admits two colorsComplete assignment space · 16 candidates

The problem

Decide and count color assignments satisfying every graph edge.

The checked result

Satisfiable: yes; Solution count: 2.

Every assignment either yields a fully valid coloring or an edge witnessing failure. Counting includes distinct color labels, so symmetric assignments remain separate.

Why the checker accepts it

  1. Enumerate one color value for each vertex.
  2. Check every edge’s unequal-color constraint.
  3. Count the complete solution space.
  4. Validate a coloring witness, or require enumeration evidence when no model exists.

Formal specification

{
  "vertices": 4,
  "edges": [
    [
      0,
      1
    ],
    [
      1,
      2
    ],
    [
      2,
      3
    ],
    [
      3,
      0
    ]
  ],
  "colors": 2
}

Claim and evidence

{
  "claim": {
    "satisfiable": true,
    "solution_count": 2
  },
  "witness": {
    "coloring": [
      0,
      1,
      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 16 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

k colors on n vertices produce kⁿ assignments. Color-label permutations can create symmetric solutions.

This is a finite coloring instance; the solution count is not reduced by graph or color symmetries.

A boundary to investigate

Failing to find a solution is not equivalent to proving there is none. Add symmetry reduction and checked propagation or conflict explanations.

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-046 ↘Related KL-FCS-048 ↘
KL-FCS-048
Constraint satisfactionFour pairwise adjacent vertices need more colorsComplete assignment space · 81 candidates

The problem

Decide and count color assignments satisfying every graph edge.

The checked result

Satisfiable: no; Solution count: 0.

Every assignment either yields a fully valid coloring or an edge witnessing failure. Counting includes distinct color labels, so symmetric assignments remain separate.

Why the checker accepts it

  1. Enumerate one color value for each vertex.
  2. Check every edge’s unequal-color constraint.
  3. Count the complete solution space.
  4. Validate a coloring witness, or require enumeration evidence when no model exists.

Formal specification

{
  "vertices": 4,
  "edges": [
    [
      0,
      1
    ],
    [
      0,
      2
    ],
    [
      0,
      3
    ],
    [
      1,
      2
    ],
    [
      1,
      3
    ],
    [
      2,
      3
    ]
  ],
  "colors": 3
}

Claim and evidence

{
  "claim": {
    "satisfiable": false,
    "solution_count": 0
  },
  "witness": {
    "method": "exhaustive enumeration"
  }
}

Dataset construction

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

Complexity and limits

k colors on n vertices produce kⁿ assignments. Color-label permutations can create symmetric solutions.

This is a finite coloring instance; the solution count is not reduced by graph or color symmetries.

A boundary to investigate

Failing to find a solution is not equivalent to proving there is none. Add symmetry reduction and checked propagation or conflict explanations.

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-046 ↘Related KL-FCS-047 ↘

Go further.

Add symmetry reduction and checked propagation or conflict explanations.

Questions to investigate

  1. Failing to find a solution is not equivalent to proving there is none.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add symmetry reduction and checked propagation or conflict explanations.

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

Circuit minimizationSchedulingCombinatorial optimization