agenticraft_foundation.complexity.bounds

30+ catalogued complexity bounds across distributed algorithm categories, fault models (4 classical + 4 LLM-specific), and impossibility results.

Complexity bounds and theoretical limits.

This module provides utilities for reasoning about complexity bounds, including lower bounds, optimality proofs, and theoretical limits for distributed algorithms.

BoundType

Bases: str, Enum

Type of complexity bound.

TheoreticalBound dataclass

A theoretical bound from distributed systems literature.

ATTRIBUTE	DESCRIPTION
problem	The problem this bound applies to TYPE: str
metric	What is being bounded (time, messages, rounds) TYPE: str
bound_type	Type of bound (upper, lower, tight) TYPE: BoundType
expression	The bound expression TYPE: str
conditions	Conditions under which bound holds TYPE: list[str]
source	Citation for the bound TYPE: str
proof_sketch	Brief description of proof technique TYPE: str

OptimalityCheck dataclass

Result of checking if an algorithm is optimal.

ATTRIBUTE	DESCRIPTION
is_optimal	Whether algorithm matches lower bound TYPE: bool
algorithm_bound	The algorithm's complexity TYPE: str
lower_bound	The theoretical lower bound TYPE: str
gap	Gap between algorithm and lower bound TYPE: str | None
conditions_match	Whether conditions match TYPE: bool
notes	Additional notes TYPE: str

ImpossibilityResult dataclass

Represents an impossibility result.

ATTRIBUTE	DESCRIPTION
problem	The impossible problem TYPE: str
conditions	Conditions making it impossible TYPE: list[str]
source	Citation TYPE: str
workarounds	Known workarounds that weaken assumptions TYPE: list[str]

ComplexityComparison dataclass

Comparison of multiple algorithm complexities.

ATTRIBUTE	DESCRIPTION
problem	The problem being solved TYPE: str
algorithms	Dict mapping algorithm name to complexity TYPE: dict[str, dict[str, str]]
optimal_for_metric	Dict mapping metric to best algorithm TYPE: dict[str, list[str]]
pareto_optimal	Algorithms that are Pareto optimal TYPE: list[str]

check_optimality(algorithm_complexity, problem, metric='messages')

Check if an algorithm achieves optimal complexity.

PARAMETER	DESCRIPTION
algorithm_complexity	The algorithm's complexity (e.g., "O(n^2)") TYPE: str
problem	The problem being solved TYPE: str
metric	The metric to check TYPE: str DEFAULT: 'messages'

RETURNS	DESCRIPTION
OptimalityCheck	OptimalityCheck with results

get_impossibility(problem)

Get impossibility result for a problem.

PARAMETER	DESCRIPTION
problem	Problem description TYPE: str

RETURNS	DESCRIPTION
ImpossibilityResult | None	ImpossibilityResult if found, None otherwise

validate_fault_tolerance(n, f, fault_model)

Validate if fault tolerance is achievable.

PARAMETER	DESCRIPTION
n	Number of nodes TYPE: int
f	Number of failures to tolerate TYPE: int
fault_model	Type of failures (crash, byzantine) TYPE: str

RETURNS	DESCRIPTION
tuple[bool, str]	Tuple of (is_valid, explanation)

compare_algorithms(problem, algorithms)

Compare complexity of multiple algorithms.

PARAMETER	DESCRIPTION
problem	The problem being solved TYPE: str
algorithms	Dict mapping algorithm name to complexity dict Example: {"PBFT": {"messages": "O(n^2)", "rounds": "O(1)"}} TYPE: dict[str, dict[str, str]]

RETURNS	DESCRIPTION
ComplexityComparison	ComplexityComparison with analysis