polynomial-time-reductions

Here is 1 public repository matching this topic...

PierreSenellart / descriptive-complexity

A Lean library for descriptive complexity: NP-completeness and the polynomial hierarchy by first-order reductions, stronger than polynomial-time (Karp) reductions. Machine-free Cook–Levin, all 21 Karp problems, on Mathlib's ModelTheory

complexity np-complete lean reductions model-theory np-completeness lean4 np-complete-problems cook-levin descriptive-complexity polynomial-time-reductions

Updated Aug 31, 2026
Lean

Add this topic to your repo

To associate your repository with the polynomial-time-reductions topic, visit your repo's landing page and select "manage topics."

Learn more