complexity.py

1import itertools2from itertools import product3from fractions import Fraction4from .bang import anf_coefficients56# COMPLEXITY MEASURES - THE STANDARD BOOLEAN-FUNCTION TOOLKIT, FROM SCRATCH78def _value(filled):9    f = filled10    def ev(x):11        return 1 if x in f else 012    return ev1314def _flip(corner, axis):15    return tuple(corner[j] ^ (1 if j == axis else 0) for j in range(len(corner)))1617# SENSITIVITY1819def sensitivity_at(filled, cells, x):20    fx = 1 if x in filled else 021    count = 022    for axis in range(len(x)):23        y = _flip(x, axis)24        fy = 1 if y in filled else 025        if fy != fx:26            count += 127    return count2829def sensitivity(filled, cells):30    return max((sensitivity_at(filled, cells, x) for x in cells), default=0)3132# BLOCK SENSITIVITY3334def _flip_block(corner, block):35    s = set(block)36    return tuple(corner[j] ^ (1 if j in s else 0) for j in range(len(corner)))3738def _sensitive_blocks(filled, cells, x):39    D = len(x)40    fx = 1 if x in filled else 041    blocks = []42    for r in range(1, D + 1):43        for block in itertools.combinations(range(D), r):44            y = _flip_block(x, block)45            fy = 1 if y in filled else 046            if fy != fx:47                blocks.append(frozenset(block))48    return blocks4950def _minimal_blocks(blocks):51    out = []52    for b in blocks:53        if not any(other < b for other in blocks):54            out.append(b)55    return out5657def _max_disjoint(blocks):58    blocks = sorted(set(blocks), key=lambda b: (len(b), tuple(sorted(b))))59    best = 060    def search(i, used, count):61        nonlocal best62        if count + (len(blocks) - i) <= best:63            return64        if i == len(blocks):65            best = max(best, count)66            return67        b = blocks[i]68        if used.isdisjoint(b):69            search(i + 1, used | b, count + 1)70        search(i + 1, used, count)71    search(0, frozenset(), 0)72    return best7374def block_sensitivity_at(filled, cells, x):75    blocks = _minimal_blocks(_sensitive_blocks(filled, cells, x))76    return _max_disjoint(blocks)7778def block_sensitivity(filled, cells):79    return max((block_sensitivity_at(filled, cells, x) for x in cells), default=0)8081# CERTIFICATE COMPLEXITY8283def _is_certificate(filled, cells, x, S):84    fx = 1 if x in filled else 085    Sset = set(S)86    for y in cells:87        if all(y[j] == x[j] for j in Sset):88            fy = 1 if y in filled else 089            if fy != fx:90                return False91    return True9293def certificate_at(filled, cells, x):94    D = len(x)95    for r in range(D + 1):96        for S in itertools.combinations(range(D), r):97            if _is_certificate(filled, cells, x, S):98                return r99    return D100101def certificate_complexity(filled, cells):102    return max((certificate_at(filled, cells, x) for x in cells), default=0)103104def certificate_complexity_1(filled, cells):105    vals = [certificate_at(filled, cells, x) for x in cells if x in filled]106    return max(vals, default=0)107108def certificate_complexity_0(filled, cells):109    vals = [certificate_at(filled, cells, x) for x in cells if x not in filled]110    return max(vals, default=0)111112# DECISION-TREE DEPTH113114def _restrict(filled_sub, axis, value):115    return frozenset(c for c in filled_sub if c[axis] == value)116117def _all_sub(cells_sub, axis, value):118    return [c for c in cells_sub if c[axis] == value]119120def _constant_value(filled_count, total_count):121    if filled_count == 0:122        return 0123    if filled_count == total_count:124        return 1125    return None126127def decision_tree_depth(filled, cells):128    D = len(cells[0]) if cells else 0129    full = frozenset(cells)130    memo = {}131    def depth(sub_cells, free_axes):132        key = (sub_cells, free_axes)133        if key in memo:134            return memo[key]135        lit = sum(1 for c in sub_cells if c in filled)136        if lit == 0 or lit == len(sub_cells):137            memo[key] = 0138            return 0139        best = None140        for axis in free_axes:141            rest = tuple(a for a in free_axes if a != axis)142            c0 = tuple(c for c in sub_cells if c[axis] == 0)143            c1 = tuple(c for c in sub_cells if c[axis] == 1)144            d = 1 + max(depth(c0, rest), depth(c1, rest))145            if best is None or d < best:146                best = d147        memo[key] = best148        return best149    return depth(tuple(cells), tuple(range(D)))150151# REAL (FOURIER) POLYNOMIAL DEGREE152153def real_anf_coefficients(filled, cells):154    D = len(cells[0])155    coeff = {c: (1 if c in filled else 0) for c in cells}156    for axis in range(D):157        for c in cells:158            if c[axis] == 1:159                lower = tuple(c[j] if j != axis else 0 for j in range(D))160                coeff[c] = coeff[c] - coeff[lower]161    return coeff162163def real_degree(filled, cells):164    coeff = real_anf_coefficients(filled, cells)165    degs = [sum(c) for c in cells if coeff[c] != 0]166    return max(degs, default=-1)167168# DNF AND CNF SIZE169170def _pattern_cells(pattern, cells):171    out = []172    for c in cells:173        if all(p == -1 or p == c[j] for j, p in enumerate(pattern)):174            out.append(c)175    return frozenset(out)176177def _prime_implicants(filled, cells):178    D = len(cells[0])179    onset = frozenset(c for c in cells if c in filled)180    current = {tuple(c) for c in onset}181    primes = []182    while current:183        used = set()184        nxt = set()185        for a in current:186            for b in current:187                if a >= b:188                    continue189                diff = [j for j in range(D) if a[j] != b[j]]190                if len(diff) == 1:191                    j = diff[0]192                    if a[j] == -1 or b[j] == -1:193                        continue194                    merged = tuple(-1 if k == j else a[k] for k in range(D))195                    nxt.add(merged)196                    used.add(a)197                    used.add(b)198        for a in current:199            if a not in used:200                primes.append(a)201        current = nxt202    out = []203    seen = set()204    for pat in primes:205        if pat in seen:206            continue207        seen.add(pat)208        out.append((pat, _pattern_cells(pat, cells)))209    return out, onset210211def _min_cover(onset, prime_covers):212    onset = frozenset(onset)213    if not onset:214        return 0215    covers = [c & onset for c in prime_covers if c & onset]216    best = [len(onset) + 1]217    def search(remaining, used):218        if not remaining:219            best[0] = min(best[0], used)220            return221        if used + 1 >= best[0]:222            return223        target = next(iter(remaining))224        options = [c for c in covers if target in c]225        options.sort(key=lambda c: len(c & remaining), reverse=True)226        for c in options:227            search(remaining - c, used + 1)228    search(onset, 0)229    return best[0]230231def dnf_size(filled, cells):232    primes, onset = _prime_implicants(filled, cells)233    if not onset:234        return 0235    return _min_cover(onset, [cov for _, cov in primes])236237def cnf_size(filled, cells):238    full = frozenset(cells)239    complement = full - frozenset(filled)240    return dnf_size(complement, cells)241242# THE FILL-POLYNOMIAL FINGERPRINT243244def _fill_at_odd_base(filled, cells, k):245    D = len(cells[0])246    E = k247    O = k - 1248    total = 0249    for c in filled:250        pc = sum(c)251        total += (E ** (D - pc)) * (O ** pc)252    return total253254def _fit_polynomial(points):255    n = len(points)256    xs = [Fraction(x) for x, _ in points]257    ys = [Fraction(y) for _, y in points]258    coeffs = [Fraction(0)] * n259    for i in range(n):260        Li = [Fraction(0)] * n261        Li[0] = Fraction(1)262        denom = Fraction(1)263        for j in range(n):264            if j == i:265                continue266            denom *= (xs[i] - xs[j])267            new = [Fraction(0)] * n268            for d in range(n - 1):269                new[d + 1] += Li[d]270            for d in range(n):271                new[d] += -xs[j] * Li[d]272            Li = new273        scale = ys[i] / denom274        for d in range(n):275            coeffs[d] += scale * Li[d]276    return coeffs277278def fill_fingerprint(filled, cells):279    D = len(cells[0])280    points = [(k, _fill_at_odd_base(filled, cells, k)) for k in range(1, D + 2)]281    coeffs = _fit_polynomial(points)282    leading_first = list(reversed(coeffs))283    cleaned = []284    for a in leading_first:285        cleaned.append(int(a) if a.denominator == 1 else a)286    return cleaned287288def measures(filled, cells):289    return {290        "popcount": len(filled),291        "sensitivity": sensitivity(filled, cells),292        "block_sensitivity": block_sensitivity(filled, cells),293        "certificate": certificate_complexity(filled, cells),294        "certificate_1": certificate_complexity_1(filled, cells),295        "certificate_0": certificate_complexity_0(filled, cells),296        "decision_tree_depth": decision_tree_depth(filled, cells),297        "real_degree": real_degree(filled, cells),298        "dnf_size": dnf_size(filled, cells),299        "cnf_size": cnf_size(filled, cells),300        "fill_fingerprint": fill_fingerprint(filled, cells),301    }