agenticraft_foundation.complexity.annotations

Complexity annotations — decorator-based tracking for algorithmic complexity classification.

Complexity annotations for algorithm documentation and analysis.

This module provides decorators and utilities for documenting and analyzing algorithm complexity, following formal verification principles from distributed systems research.

Example

@complexity( time="O(D * log n)", space="O(n)", messages="Theta(n^2)", rounds="O(D)", assumptions=["partial synchrony", "f < n/3 Byzantine"], theorem_ref="Castro & Liskov 1999" ) async def propose(self, value, context): ...

ComplexityClass

Bases: str, Enum

Standard complexity classes.

SynchronyModel

Bases: str, Enum

Synchrony assumptions for distributed algorithms.

FaultModel

Bases: str, Enum

Fault tolerance models.

Classical distributed systems fault models: - CRASH_STOP: Process halts, never recovers (f < n/2) - CRASH_RECOVERY: Process halts, may recover with stable storage (f < n/2) - BYZANTINE: Arbitrary behavior including malicious (f < n/3) - OMISSION: Process fails to send or receive messages (f < n/2) - AUTHENTICATED_BYZANTINE: Byzantine with digital signatures (f < n/3)

LLM-specific fault models (map to classical analogs): - HALLUCINATION: Generates plausible but incorrect output (analog: Byzantine — arbitrary incorrect responses) - PROMPT_INJECTION: Adversarial input manipulates behavior (analog: Byzantine — attacker-controlled behavior) - NON_DETERMINISM: Same input yields different outputs across calls (analog: Omission — unreliable message content) - CONTEXT_OVERFLOW: Input exceeds context window, truncating information (analog: Crash-Recovery — partial state loss, recoverable with chunking)

ComplexityBound dataclass

Represents a complexity bound with optional proof reference.

ATTRIBUTE	DESCRIPTION
expression	The complexity expression (e.g., "O(n log n)") TYPE: str
tight	Whether this is a tight bound (Theta vs O) TYPE: bool
amortized	Whether this is amortized complexity TYPE: bool
expected	Whether this is expected (average) complexity TYPE: bool
worst_case	Whether this is worst-case complexity TYPE: bool
proof_ref	Reference to proof (paper, theorem number) TYPE: str | None
notes	Additional notes about the bound TYPE: str | None

__str__()

Format the complexity bound as a string.

parse(expr) classmethod

Parse a complexity expression string.

PARAMETER	DESCRIPTION
expr	Complexity expression like "O(n log n)" or "Theta(n^2)" TYPE: str

RETURNS	DESCRIPTION
ComplexityBound	ComplexityBound instance

DistributedComplexity dataclass

Complexity metrics specific to distributed algorithms.

ATTRIBUTE	DESCRIPTION
time	Time complexity (sequential operations) TYPE: ComplexityBound | str | None
space	Space complexity per node TYPE: ComplexityBound | str | None
messages	Total message complexity TYPE: ComplexityBound | str | None
message_size	Size of individual messages TYPE: ComplexityBound | str | None
rounds	Round/communication complexity TYPE: ComplexityBound | str | None
bits	Total bit complexity TYPE: ComplexityBound | str | None
synchrony	Required synchrony model TYPE: SynchronyModel | str | None
fault_model	Assumed fault model TYPE: FaultModel | str | None
fault_tolerance	Maximum faults tolerated (e.g., "f < n/3") TYPE: str | None
assumptions	List of additional assumptions TYPE: list[str]
theorem_ref	Reference to theorem/paper TYPE: str | None
lower_bound	Known lower bound for the problem TYPE: str | None
optimal	Whether this achieves the lower bound TYPE: bool

__post_init__()

Convert string bounds to ComplexityBound objects.

to_dict()

Convert to dictionary for serialization.

format_docstring()

Format complexity information for docstring inclusion.

ComplexityAnalysis dataclass

Results of complexity analysis on a codebase.

summary()

Generate summary report.

get_complexity(func)

Get complexity annotation for a function.

PARAMETER	DESCRIPTION
func	The annotated function TYPE: Callable[..., Any]

RETURNS	DESCRIPTION
DistributedComplexity | None	DistributedComplexity if annotated, None otherwise

get_all_complexities()

Get all registered complexity annotations.

RETURNS	DESCRIPTION
dict[str, DistributedComplexity]	Dictionary mapping function keys to complexity info

complexity(time=None, space=None, messages=None, message_size=None, rounds=None, bits=None, synchrony=None, fault_model=None, fault_tolerance=None, assumptions=None, theorem_ref=None, lower_bound=None, optimal=False)

Decorator to annotate function with complexity information.

This decorator documents algorithm complexity for formal analysis and documentation purposes. It stores the complexity information in a registry for later retrieval.

PARAMETER	DESCRIPTION
time	Time complexity (e.g., "O(n log n)") TYPE: str | ComplexityBound | None DEFAULT: None
space	Space complexity per node TYPE: str | ComplexityBound | None DEFAULT: None
messages	Total message complexity TYPE: str | ComplexityBound | None DEFAULT: None
message_size	Size of individual messages TYPE: str | ComplexityBound | None DEFAULT: None
rounds	Round/communication complexity TYPE: str | ComplexityBound | None DEFAULT: None
bits	Total bit complexity TYPE: str | ComplexityBound | None DEFAULT: None
synchrony	Required synchrony model TYPE: SynchronyModel | str | None DEFAULT: None
fault_model	Assumed fault model TYPE: FaultModel | str | None DEFAULT: None
fault_tolerance	Maximum faults tolerated TYPE: str | None DEFAULT: None
assumptions	Additional assumptions TYPE: list[str] | None DEFAULT: None
theorem_ref	Reference to theorem/paper TYPE: str | None DEFAULT: None
lower_bound	Known lower bound TYPE: str | None DEFAULT: None
optimal	Whether this achieves lower bound TYPE: bool DEFAULT: False

RETURNS	DESCRIPTION
Callable[[Callable[P, R]], Callable[P, R]]	Decorated function with complexity metadata

Example

@complexity( time="O(n^2)", messages="O(n^2)", rounds="O(1)", fault_model=FaultModel.BYZANTINE, fault_tolerance="f < n/3", theorem_ref="Castro & Liskov 1999, PBFT" ) async def pbft_prepare(self, request): ...

consensus_complexity(algorithm, fault_tolerance='f < n/3', synchrony=SynchronyModel.PARTIAL_SYNCHRONY)

Specialized complexity decorator for consensus algorithms.

Provides preset complexity bounds for common consensus algorithms.

PARAMETER	DESCRIPTION
algorithm	Name of consensus algorithm (raft, pbft, paxos, etc.) TYPE: str
fault_tolerance	Fault tolerance bound TYPE: str DEFAULT: 'f < n/3'
synchrony	Synchrony model TYPE: SynchronyModel DEFAULT: PARTIAL_SYNCHRONY

RETURNS	DESCRIPTION
Callable[[Callable[P, R]], Callable[P, R]]	Complexity decorator with preset values

gossip_complexity(fanout=3, rounds='O(log n)')

Specialized complexity decorator for gossip protocols.

PARAMETER	DESCRIPTION
fanout	Number of nodes to contact per round TYPE: int DEFAULT: 3
rounds	Expected rounds to convergence TYPE: str DEFAULT: 'O(log n)'

RETURNS	DESCRIPTION
Callable[[Callable[P, R]], Callable[P, R]]	Complexity decorator with gossip-specific values

analyze_complexity(module)

Analyze complexity annotations in a module.

PARAMETER	DESCRIPTION
module	Python module to analyze TYPE: Any

RETURNS	DESCRIPTION
ComplexityAnalysis	ComplexityAnalysis with results

parse_big_o(expression)

Parse a Big-O expression into components.

PARAMETER	DESCRIPTION
expression	Big-O expression like "O(n^2 log n)" TYPE: str

RETURNS	DESCRIPTION
tuple[str, dict[str, Any]]	Tuple of (base_class, parameters)

Example

parse_big_o("O(n^2 log n)") ('polynomial_log', {'exponent': 2, 'log_factor': True})

compare_complexity(a, b)

Compare two complexity expressions.

PARAMETER	DESCRIPTION
a	First complexity expression TYPE: str
b	Second complexity expression TYPE: str

RETURNS	DESCRIPTION
int	-1 if a < b, 0 if equal, 1 if a > b