Expand description
Auto-generated module
🤖 Generated with SplitRS
Structs§
- Circuit
Evaluator - Evaluate a Boolean circuit on a given input assignment.
- Circuit
Gate - Communication
Matrix Analyzer - Compute rank-based lower bounds for communication complexity. Uses Gaussian elimination over GF(2) to find rank of the communication matrix.
- Dpll
Solver - DPLL-based propositional SAT solver. Variables are 1..=n. Clauses are lists of literals (positive = var, negative = -var).
- Parameterized
Algorithm Checker - Check whether an algorithm runs within FPT time bound f(k) * n^c. Accepts observed runtime, parameter k, input size n, computable f, and constant c.
- Resolution
Prover Small - Simple resolution-based propositional prover. Works on clauses over integer literals (positive = var, negative = negated var). Attempts to derive the empty clause (refutation).
- Sensitivity
Checker - Compute sensitivity and block sensitivity of a Boolean function. The function is given as a truth table (index = bit string, value = output).
- Sudoku
Solver - Simple Sudoku solver using backtracking (9×9).
- TwoSat
Solver - Evaluate a 2-CNF formula (given as list of clauses over bool variables).
Returns
trueif satisfiable (2-SAT, solved via Kosaraju SCC).
Enums§
- Gate
Kind - Evaluate a Boolean circuit represented as a DAG.
Gates: 0 = AND, 1 = OR, 2 = NOT, 3 = INPUT (index stored in
left).