Heuristic Complexity Mapping of MCSP

Highlights

• Truth tables & circuits: bitset-backed truth tables, gate-level circuits, and And-Inverter Graphs.
• Exact SAT solver: Z3 encoding with binary search over circuit size.
• Quine–McCluskey: prime implicants + Petrick's method to build minimal SOP circuits.
• Genetic solver: population search balancing correctness and circuit size.
• Analysis: complexity landscape sampling, hardness index, and plotting hooks.
• ML baselines: MLP / Transformer predictors over truth tables and dataset generation utilities.

Visual snapshots

Compact, at-a-glance graphs from recent MCSP sampling runs.

Run the demo

pip install -r requirements.txt      # z3/torch optional (torch not needed for tests)
python main.py                       # runs truth tables, SAT/QMC/GA solvers, analysis, and ML demo

Want something faster? Run individual components:

python -m pytest                     # full test suite
python -c "from mcsp.core.truth_table import TruthTable; print(TruthTable.parity(3))"
python -c "from mcsp.solvers.sat_solver import MCSPSatSolver, TruthTable; 
solver = MCSPSatSolver(2, 5); 
print(solver.find_minimum_circuit(TruthTable(2, [0,1,1,0])))"

How the mapping works

1. Encode: circuits become SAT constraints (gate type, wiring, input/output consistency).
2. Solve: either exact SAT (Z3), Quine–McCluskey, or a genetic search builds candidate circuits.
3. Validate: synthesized circuits are checked against the target truth table.
4. Analyze: we sample random functions, summarize complexity stats, and compute a hardness index relative to 2^n / n.

GitHub Pages

1. In GitHub, open Settings → Pages.
2. Set Source to main and Folder to /docs.
3. Publish. The site will be live at:
   https://arnavd371.github.io/Heuristic-Complexity-Mapping-of-MCSP/

The page you are reading is fully self-contained; update this file to refresh the site.

Repository links

• Source code on GitHub
• README