Concept icon
Concept

Counting factor-variable incidences before choosing schedules

The scope I_f is the set of original variables a factor may read. An incidence is a distinct pair (f,v) with v in I_f. Let n>=1 be the number of variables, M=sum_f |I_f|, and positive integers w,b bound each scope size and the number of factors containing any one variable. Scope size is not polynomial degree: a factor reading only x can contain x^100. If necessary, add a distinct constant-one factor with declared scope {v} for every variable. This preserves the product, increases b by at most one, and increases M by n. Using b after this addition gives n<=M<=bn. Empty-scope factors need no auxiliary slot and can be assigned to group one.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math