boofun.analysis.complexity

Complexity measures for Boolean functions.

This module implements various complexity measures including: - Decision tree depth (deterministic query complexity) - Decision tree size - Sensitivity and block sensitivity - Certificate complexity

These are fundamental measures in computational complexity theory as discussed in O’Donnell’s book and related literature.

Functions

average_sensitivity(f)	Compute the average sensitivity of f.
certificate_complexity(f, x)	Compute the certificate complexity at input x.
decision_tree_depth(f)	Compute the optimal deterministic decision tree depth for function f.
decision_tree_size(f[, minimize_depth_first])	Compute the optimal decision tree size for function f.
max_certificate_complexity(f[, value])	Compute the maximum certificate complexity of f.
max_sensitivity(f[, value])	Compute the maximum sensitivity of f.
min_sensitivity(f[, value])	Compute the minimum sensitivity of f (over non-trivial inputs).
sensitivity(f, x)	Compute the sensitivity of f at input x.

Classes

ComplexityProfile(f)

Compute and store various complexity measures for a Boolean function.

boofun.analysis.complexity.decision_tree_depth(f: BooleanFunction) → int

Compute the optimal deterministic decision tree depth for function f.

The decision tree depth D(f) is the minimum number of adaptive queries needed to compute f on any input in the worst case.

This uses dynamic programming over sub-cubes, computing the optimal depth for all partial assignments simultaneously.

Parameters:

f – BooleanFunction to analyze

Returns:

Optimal decision tree depth

Note

Time complexity: O(3^n) where n is the number of variables. Memory complexity: O(3^n)

Example

>>> majority = bf.BooleanFunctionBuiltins.majority(3)
>>> decision_tree_depth(majority)
2  # Can determine majority with 2 queries

boofun.analysis.complexity.decision_tree_size(f: BooleanFunction, minimize_depth_first: bool = False) → Tuple[int, int]

Compute the optimal decision tree size for function f.

Parameters:

• f – BooleanFunction to analyze

• minimize_depth_first – If True, minimize depth first, then size. If False, minimize size first, then depth.

Returns:

Tuple of (size, depth) where size is the number of leaves

Note

Size measures the total number of leaves in the decision tree, while depth measures the longest root-to-leaf path.

boofun.analysis.complexity.sensitivity(f: BooleanFunction, x: int) → int

Compute the sensitivity of f at input x.

The sensitivity s(f, x) counts how many single-bit flips change the output.

Parameters:

• f – BooleanFunction to analyze

• x – Input index (integer representation)

Returns:

Number of sensitive coordinates at x

boofun.analysis.complexity.max_sensitivity(f: BooleanFunction, value: int | None = None) → int

Compute the maximum sensitivity of f.

Parameters:

• f – BooleanFunction to analyze

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

Returns:

Maximum sensitivity across all (relevant) inputs

boofun.analysis.complexity.min_sensitivity(f: BooleanFunction, value: int | None = None) → int

Compute the minimum sensitivity of f (over non-trivial inputs).

Parameters:

• f – BooleanFunction to analyze

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

Returns:

Minimum sensitivity across relevant inputs

boofun.analysis.complexity.average_sensitivity(f: BooleanFunction) → float

Compute the average sensitivity of f.

The average sensitivity equals the total influence I(f) = sum_i Inf_i(f).

Parameters:

f – BooleanFunction to analyze

Returns:

Average sensitivity (total influence)

boofun.analysis.complexity.certificate_complexity(f: BooleanFunction, x: int) → Tuple[int, List[int]]

Compute the certificate complexity at input x.

A certificate for f at x is a minimal set of coordinates S such that fixing the coordinates in S to their values in x determines f.

Parameters:

• f – BooleanFunction to analyze

• x – Input index

Returns:

Tuple of (certificate_size, list_of_certificate_variables)

class boofun.analysis.complexity.ComplexityProfile(f: BooleanFunction)

Compute and store various complexity measures for a Boolean function.

This class provides a comprehensive analysis of function complexity, computing multiple measures and checking known relationships between them.

__init__(f: BooleanFunction)

Initialize and compute complexity profile.

Parameters:

f – BooleanFunction to analyze

compute() → Dict[str, Any]

Compute all complexity measures.

Returns:

Dictionary of complexity measures

summary() → str

Return a human-readable summary of complexity measures.

check_relations() → Dict[str, bool]

Check known relationships between complexity measures.

Returns:

Dictionary of relationship checks