boofun.analysis.certificates

Certificate utilities (exact search for modest n).

Functions

certificate(f, x)

Return a minimal certificate size and variables for input x.

max_certificate_size(f)

Maximum certificate size across inputs.

min_certificate_size(f[, value])

Minimum certificate size across inputs.
boofun.analysis.certificates.certificate(f: BooleanFunction, x: int) → Tuple[int, List[int]][source]

Return a minimal certificate size and variables for input x.

boofun.analysis.certificates.max_certificate_size(f: BooleanFunction) → int[source]

Maximum certificate size across inputs.

boofun.analysis.certificates.min_certificate_size(f: BooleanFunction, value: int | None = None) → int[source]

Minimum certificate size across inputs.

Parameters:

  • f – BooleanFunction to analyze

  • value – If specified (0 or 1), only consider inputs where f(x) = value

Returns:

Minimum certificate complexity

References

  • Tal’s BooleanFunc.py: min_certificate