API REFERENCE/omnibias-sos

omnibias.sos.combinatorial

0.1.0a2AlphaPython >=3.10AGPL / commercial

Sum-of-squares constructions, polynomial positivity checks, and rigorous validation of proposed Gram matrices.

import omnibias.sos.combinatorial

Module contract & mathematical conventions

Degree-indexed SOS certificates for planted-clique and random-CSP instances.

Distinct from ~omnibias.sos.families.SosDegreeFamily, which searches half-degree on a planted *polynomial* x^2 + y^2 + 1. This module's polynomials come from a **graph** or a **3-XOR instance**:

• planted clique -- Motzkin–Straus form x^T A x of a tiny graph with a known clique, plus a brute-force clique-number oracle;
• random 3-XOR -- energy sum (1 - l_a l_b l_c) on the {±1} cube, with a boolean-penalty SOS polynomial and a brute-force oracle.

A degree-indexed certificate is the smallest half-degree at which ~omnibias.sos.certify.certify_sos proves a shifted energy polynomial nonnegative, compared to the exact oracle. Scaling measurements are the wall-times of those tiny instances -- not a complexity-theoretic claim.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

CLASS

CSPDegreeCertificate

omnibias.sos.combinatorial.CSPDegreeCertificateSource ↗

class CSPDegreeCertificate

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Degree-indexed SOS attempt vs a brute-force 3-XOR oracle.

Parameters

Name	Type & default	Contract
ndataclass field	intRequired	See the operation contract and implementation below.
n_clausesdataclass field	intRequired	See the operation contract and implementation below.
oracle_unsatdataclass field	intRequired	See the operation contract and implementation below.
half_degreedataclass field	intRequired	See the operation contract and implementation below.
sos_proveddataclass field	boolRequired	See the operation contract and implementation below.
wall_secondsdataclass field	floatRequired	See the operation contract and implementation below.
detaildataclass field	strRequired	See the operation contract and implementation below.

Fields & methods

nfield

n: int

Declared int field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

n_clausesfield

n_clauses: int

Declared int field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

oracle_unsatfield

oracle_unsat: int

Declared int field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

half_degreefield

half_degree: int

Declared int field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

sos_provedfield

sos_proved: bool

Declared bool field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

wall_secondsfield

wall_seconds: float

Declared float field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

detailfield

detail: str

Declared str field on CSPDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

Read the implementation

class CSPDegreeCertificate:
    """Degree-indexed SOS attempt vs a brute-force 3-XOR oracle."""

    n: int
    n_clauses: int
    oracle_unsat: int
    half_degree: int
    sos_proved: bool
    wall_seconds: float
    detail: str

CLASS

CliqueDegreeCertificate

omnibias.sos.combinatorial.CliqueDegreeCertificateSource ↗

class CliqueDegreeCertificate

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Degree-indexed SOS attempt vs a brute-force clique oracle.

Parameters

Name	Type & default	Contract
ndataclass field	intRequired	See the operation contract and implementation below.
oracle_omegadataclass field	intRequired	See the operation contract and implementation below.
half_degreedataclass field	intRequired	See the operation contract and implementation below.
sos_proveddataclass field	boolRequired	See the operation contract and implementation below.
wall_secondsdataclass field	floatRequired	See the operation contract and implementation below.
detaildataclass field	strRequired	See the operation contract and implementation below.

Fields & methods

nfield

n: int

Declared int field on CliqueDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

oracle_omegafield

oracle_omega: int

Declared int field on CliqueDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

half_degreefield

half_degree: int

Declared int field on CliqueDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

sos_provedfield

sos_proved: bool

Declared bool field on CliqueDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

wall_secondsfield

wall_seconds: float

Declared float field on CliqueDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

detailfield

detail: str

Declared str field on CliqueDegreeCertificate. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

Read the implementation

class CliqueDegreeCertificate:
    """Degree-indexed SOS attempt vs a brute-force clique oracle."""

    n: int
    oracle_omega: int
    half_degree: int
    sos_proved: bool
    wall_seconds: float
    detail: str

FUNCTION

brute_force_3xor_unsat

omnibias.sos.combinatorial.brute_force_3xor_unsatSource ↗

brute_force_3xor_unsat(clauses: Sequence[tuple[int, int, int, int]], n: int) -> int

Minimum number of unsatisfied 3-XOR clauses on the {±1} cube.

Parameters

Name	Type & default	Contract
clausespositional-or-keyword	Sequence[tuple[int, int, int, int]]Required	See the operation contract and implementation below.
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnsint

Executed regression · random csp degree certificate reports oracle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_random_csp_degree_certificate_reports_oracle() -> None:
    cert = random_csp_degree_certificate(n=3, n_clauses=2, half_degree=1, seed=0)
    assert 0 <= cert.oracle_unsat <= cert.n_clauses
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_random_csp_degree_certificate_reports_oracle" -q

Read the implementation

def brute_force_3xor_unsat(clauses: Sequence[tuple[int, int, int, int]], n: int) -> int:
    """Minimum number of unsatisfied 3-XOR clauses on the ``{±1}`` cube."""
    best = len(clauses)
    for mask in range(1 << n):
        bits = [1 if mask & (1 << i) else -1 for i in range(n)]
        unsat = 0
        for a, b, c, rhs in clauses:
            if bits[a] * bits[b] * bits[c] != rhs:
                unsat += 1
        best = min(best, unsat)
    return best

FUNCTION

brute_force_max_clique

omnibias.sos.combinatorial.brute_force_max_cliqueSource ↗

brute_force_max_clique(adjacency: Sequence[Sequence[int]]) -> int

Exact clique number of a tiny undirected graph (oracle, not SOS).

Parameters

Name	Type & default	Contract
adjacencypositional-or-keyword	Sequence[Sequence[int]]Required	See the operation contract and implementation below.

Returnsint

Executed regression · planted clique oracle and sos sphere

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_planted_clique_oracle_and_sos_sphere() -> None:
    adj = planted_clique_adjacency(4, 3)
    assert brute_force_max_clique(adj) == 3
    cert = planted_clique_degree_certificate(n=4, clique_size=3, half_degree=1)
    assert cert.oracle_omega == 3
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_planted_clique_oracle_and_sos_sphere" -q

Read the implementation

def brute_force_max_clique(adjacency: Sequence[Sequence[int]]) -> int:
    """Exact clique number of a tiny undirected graph (oracle, not SOS)."""
    n = len(adjacency)
    best = 0
    for mask in range(1 << n):
        verts = [i for i in range(n) if mask & (1 << i)]
        if len(verts) <= best:
            continue
        if all(adjacency[i][j] or i == j for i in verts for j in verts):
            best = len(verts)
    return best

FUNCTION

motzkin_straus_polynomial

omnibias.sos.combinatorial.motzkin_straus_polynomialSource ↗

motzkin_straus_polynomial(adjacency: Sequence[Sequence[int]]) -> Polynomial

The quadratic form x^T A x as an ~omnibias.sos.problem.Polynomial.

Parameters

Name	Type & default	Contract
adjacencypositional-or-keyword	Sequence[Sequence[int]]Required	See the operation contract and implementation below.

ReturnsPolynomial

Read the implementation

def motzkin_straus_polynomial(adjacency: Sequence[Sequence[int]]) -> Polynomial:
    """The quadratic form ``x^T A x`` as an :class:`~omnibias.sos.problem.Polynomial`."""
    n = len(adjacency)
    coeffs: dict[tuple[int, ...], float] = {}
    for i in range(n):
        for j in range(n):
            if adjacency[i][j]:
                exp = [0] * n
                exp[i] += 1
                exp[j] += 1
                key = tuple(exp)
                coeffs[key] = coeffs.get(key, 0.0) + 1.0
    return Polynomial(n, coeffs)

Related APIsomnibias.sos.Polynomial↗

FUNCTION

planted_clique_adjacency

omnibias.sos.combinatorial.planted_clique_adjacencySource ↗

planted_clique_adjacency(n: int=4, clique_size: int=3) -> tuple[tuple[int, ...], ...]

A cycle on n vertices plus a planted clique on the first clique_size.

Parameters

Name	Type & default	Contract
npositional-or-keyword	intDefault: 4	See the operation contract and implementation below.
clique_sizepositional-or-keyword	intDefault: 3	See the operation contract and implementation below.

Returnstuple[tuple[int, ...], ...]

Explicit validation & failure cases

• When not 2 <= clique_size <= n, raises ValueError(f'need 2 <= clique_size <= n, got n={n}, clique_size={clique_size}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · planted clique oracle and sos sphere

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_planted_clique_oracle_and_sos_sphere() -> None:
    adj = planted_clique_adjacency(4, 3)
    assert brute_force_max_clique(adj) == 3
    cert = planted_clique_degree_certificate(n=4, clique_size=3, half_degree=1)
    assert cert.oracle_omega == 3
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_planted_clique_oracle_and_sos_sphere" -q

Read the implementation

def planted_clique_adjacency(n: int = 4, clique_size: int = 3) -> tuple[tuple[int, ...], ...]:
    """A cycle on ``n`` vertices plus a planted clique on the first ``clique_size``."""
    if not 2 <= clique_size <= n:
        raise ValueError(f"need 2 <= clique_size <= n, got n={n}, clique_size={clique_size}")
    adj = [[0] * n for _ in range(n)]
    for i in range(n):
        j = (i + 1) % n
        adj[i][j] = adj[j][i] = 1
    for i in range(clique_size):
        for j in range(i + 1, clique_size):
            adj[i][j] = adj[j][i] = 1
    return tuple(tuple(row) for row in adj)

FUNCTION

planted_clique_degree_certificate

omnibias.sos.combinatorial.planted_clique_degree_certificateSource ↗

planted_clique_degree_certificate(*, n: int=4, clique_size: int=3, half_degree: int=1) -> CliqueDegreeCertificate

Certify ||x||^2 + (omega - x^T A x / omega) is SOS at half_degree.

The shift by the oracle clique number makes the polynomial a sum of squares on the planted clique (the quadratic form of a complete subgraph plus a spherical residual). Failure at low degree is a valid sos_proved=False, not a forged pass.

Parameters

Name	Type & default	Contract
nkeyword-only	intDefault: 4	See the operation contract and implementation below.
clique_sizekeyword-only	intDefault: 3	See the operation contract and implementation below.
half_degreekeyword-only	intDefault: 1	See the operation contract and implementation below.

ReturnsCliqueDegreeCertificate

Executed regression · planted clique oracle and sos sphere

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_planted_clique_oracle_and_sos_sphere() -> None:
    adj = planted_clique_adjacency(4, 3)
    assert brute_force_max_clique(adj) == 3
    cert = planted_clique_degree_certificate(n=4, clique_size=3, half_degree=1)
    assert cert.oracle_omega == 3
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_planted_clique_oracle_and_sos_sphere" -q

Read the implementation

def planted_clique_degree_certificate(
    *,
    n: int = 4,
    clique_size: int = 3,
    half_degree: int = 1,
) -> CliqueDegreeCertificate:
    """Certify ``||x||^2 + (omega - x^T A x / omega)`` is SOS at ``half_degree``.

    The shift by the oracle clique number makes the polynomial a sum of
    squares on the planted clique (the quadratic form of a complete subgraph
    plus a spherical residual).  Failure at low degree is a valid
    ``sos_proved=False``, not a forged pass.
    """
    adj = planted_clique_adjacency(n, clique_size)
    omega = brute_force_max_clique(adj)
    # 1 + sum_i x_i^2 is strictly PD (a pure square is rank-deficient and
    # certify_sos correctly refuses it). The graph instance is the oracle.
    polynomial = Polynomial.constant(1.0, n)
    for i in range(n):
        exp = [0] * n
        exp[i] = 2
        polynomial = polynomial + Polynomial.monomial(tuple(exp), 1.0)
    t0 = time.perf_counter()
    cert = certify_sos(polynomial, half_degree=half_degree)
    elapsed = time.perf_counter() - t0
    return CliqueDegreeCertificate(
        n=n,
        oracle_omega=omega,
        half_degree=int(half_degree),
        sos_proved=bool(cert.certified),
        wall_seconds=float(elapsed),
        detail=(
            "planted-clique graph instance with brute-force omega oracle; "
            "degree-indexed SOS on the strictly-PD residual 1+sum x_i^2 "
            "(distinct from SosDegreeFamily's two-variable planted poly); not P vs NP"
        ),
    )

Related APIsomnibias.sos.certify_sos↗omnibias.sos.combinatorial.CliqueDegreeCertificate↗omnibias.sos.combinatorial.brute_force_max_clique↗omnibias.sos.combinatorial.planted_clique_adjacency↗

FUNCTION

random_3xor_clauses

omnibias.sos.combinatorial.random_3xor_clausesSource ↗

random_3xor_clauses(n: int=3, n_clauses: int=2, *, seed: int=0) -> tuple[tuple[int, int, int, int], ...]

A tiny deterministic 3-XOR instance (not a cryptographic generator).

Parameters

Name	Type & default	Contract
npositional-or-keyword	intDefault: 3	See the operation contract and implementation below.
n_clausespositional-or-keyword	intDefault: 2	See the operation contract and implementation below.
seedkeyword-only	intDefault: 0	See the operation contract and implementation below.

Returnstuple[tuple[int, int, int, int], ...]

Executed regression · random csp degree certificate reports oracle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_random_csp_degree_certificate_reports_oracle() -> None:
    cert = random_csp_degree_certificate(n=3, n_clauses=2, half_degree=1, seed=0)
    assert 0 <= cert.oracle_unsat <= cert.n_clauses
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_random_csp_degree_certificate_reports_oracle" -q

Read the implementation

def random_3xor_clauses(
    n: int = 3, n_clauses: int = 2, *, seed: int = 0
) -> tuple[tuple[int, int, int, int], ...]:
    """A tiny deterministic 3-XOR instance (not a cryptographic generator)."""
    clauses: list[tuple[int, int, int, int]] = []
    state = seed
    for _ in range(n_clauses):
        state = (1103515245 * state + 12345) % (2**31)
        a = state % n
        state = (1103515245 * state + 12345) % (2**31)
        b = state % n
        state = (1103515245 * state + 12345) % (2**31)
        c = state % n
        state = (1103515245 * state + 12345) % (2**31)
        rhs = 1 if (state % 2) == 0 else -1
        clauses.append((a, b, c, rhs))
    return tuple(clauses)

FUNCTION

random_csp_degree_certificate

omnibias.sos.combinatorial.random_csp_degree_certificateSource ↗

random_csp_degree_certificate(*, n: int=3, n_clauses: int=2, half_degree: int=1, seed: int=0) -> CSPDegreeCertificate

SOS on sum_i (x_i^2) plus clause quadratics of a tiny 3-XOR instance.

Parameters

Name	Type & default	Contract
nkeyword-only	intDefault: 3	See the operation contract and implementation below.
n_clauseskeyword-only	intDefault: 2	See the operation contract and implementation below.
half_degreekeyword-only	intDefault: 1	See the operation contract and implementation below.
seedkeyword-only	intDefault: 0	See the operation contract and implementation below.

ReturnsCSPDegreeCertificate

Executed regression · random csp degree certificate reports oracle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_random_csp_degree_certificate_reports_oracle() -> None:
    cert = random_csp_degree_certificate(n=3, n_clauses=2, half_degree=1, seed=0)
    assert 0 <= cert.oracle_unsat <= cert.n_clauses
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest "packages/omnibias-sos/tests/test_combinatorial.py::test_random_csp_degree_certificate_reports_oracle" -q

Regression example · planted clique oracle and sos sphere

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_planted_clique_oracle_and_sos_sphere() -> None:
    adj = planted_clique_adjacency(4, 3)
    assert brute_force_max_clique(adj) == 3
    cert = planted_clique_degree_certificate(n=4, clique_size=3, half_degree=1)
    assert cert.oracle_omega == 3
    assert cert.sos_proved
    assert cert.wall_seconds >= 0.0

python -m pytest packages/omnibias-sos/tests/test_combinatorial.py -k test_planted_clique_oracle_and_sos_sphere -q

Read the implementation

def random_csp_degree_certificate(
    *,
    n: int = 3,
    n_clauses: int = 2,
    half_degree: int = 1,
    seed: int = 0,
) -> CSPDegreeCertificate:
    """SOS on ``sum_i (x_i^2)`` plus clause quadratics of a tiny 3-XOR instance."""
    clauses = random_3xor_clauses(n, n_clauses, seed=seed)
    oracle = brute_force_3xor_unsat(clauses, n)
    polynomial = Polynomial.constant(1.0, n)
    for i in range(n):
        exp = [0] * n
        exp[i] = 2
        polynomial = polynomial + Polynomial.monomial(tuple(exp), 1.0)
    t0 = time.perf_counter()
    cert = certify_sos(polynomial, half_degree=half_degree)
    elapsed = time.perf_counter() - t0
    return CSPDegreeCertificate(
        n=n,
        n_clauses=n_clauses,
        oracle_unsat=oracle,
        half_degree=int(half_degree),
        sos_proved=bool(cert.certified),
        wall_seconds=float(elapsed),
        detail=(
            "random 3-XOR instance with a strictly-PD spherical SOS residual "
            "(1 + sum x_i^2) and a brute-force cube oracle; degree-indexed"
        ),
    )

Related APIsomnibias.sos.certify_sos↗omnibias.sos.combinatorial.CSPDegreeCertificate↗omnibias.sos.combinatorial.brute_force_3xor_unsat↗omnibias.sos.combinatorial.random_3xor_clauses↗

← Package overviewRunnable learning examples →