computational-complexity

A command line tool for computational hard problems and their reductions

Lectures for the "Problem Solving" Class at Nanjing University.

Integer multiplication below n log n: a conditional witness kappa = 6685733/10^10 (> 2^-11) for T(n) = O(n (log n)^(1-kappa)) in the multitape model, building on OpenAI's problem and Colkitt's integer-mult-bounds: certificates, independent replays, Lean 4 checks

Efficient zero-knowledge arguments in the discrete log setting, revisited

Experimental Subset Sum solver for large integers using SQLite as an out-of-core storage engine.

This repository was setup to help people who believe that they solved the P vs NP problem and to help the people who review proposed solutions.

Position-Candidate-Hypothesis (PCH) is a theoretical paradigm for structural-statistical analysis of NP-complete problems.

Circuits, Proofs, and Algebra: research papers and reproducible code on complexity lower bounds, motivated by P vs NP and VP vs VNP.

CA and Problem Sheets assigned to expedite the learning of the Theory of Computation, formally named the Theory of Algorithms. Fourth Year, Theory of Algorithms, Software Development.

A C++ program that efficiently calculates the average values of nodes at each level in a binary tree, employing a level-order traversal approach for accurate and fast computation.

Machine-checked Lean 4 formalization of TSP complexity barriers, Held-Karp integrality gap (Petersen graph), and Christofides 3/2-approximation (0 sorries).

Research implementation of the Yang–Zhang 23-Wang-tile reduction: verified region construction, deterministic C solver, and independent tiling verification.

Reproducibility companion for claim–evidence consistency in labeled graphs: complexity, certificates, correction, graph algorithms, and deterministic validation.

Trackability regimes for single-cell perturbation prediction: LAOT, synthetic phase transitions, and biological benchmarks.

A public copy of the trend-prof empirical computational complexity measurement tool

AI-assisted research notebook mapping P vs NP: proof barriers, adversarial falsification, reproducible experiments, formal verification, and a graveyard of failed ideas.

Push_swap is a project about sorting data on a stack, with a limited set of instructions, using the lowest possible number of actions. Its goal is reaching an optimized data sorting solution.

A program that sorts a stack of numbers using a minimal set of operations

Mathematics-Backed Peer to Peer Network — Rust node, marketplace, Lean 4 verified math

An experimental greedy heuristic for graph 3-coloring using a custom Matrix Sorting Machine priority structure, with benchmarking and graph visualization.