Answer: Polynomial-time solvable, with maximum objective value \(1\); a conservative running-time bound is \(O(\tau m^2L^2)\) bit operations.
Proposition 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet ≻be a preference relation over X. If the induced CO-net, ϕ∗ ≻, is conditionally acyclic, then, for every u ∈U for every U ⊆X, opt(u, ≻) = FSopt(u, ϕ∗ ≻).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a product with finite attribute set \(X\) and finite domains, and a distribution over \(\tau\) exact request types with rational masses \(\mu_t>0\) summing to \(1\), where each type \(t\) has a partial configuration \(u_t\) and a conditionally acyclic CO-net \(N_t\), choose a complete product \(f(t)\supseteq u_t\) for each type to maximize \(\sum_{t=1}^{\tau}\mu_t\mathbf{1}[f(t)=\operatorname{FSopt}(u_t,N_t)]\).
Let \(X\) be a set of \(m\) attributes, each with an explicitly listed domain \(D_A\) satisfying \(2\leq |D_A|\leq d\); a complete product assigns a value to every attribute.
A society is given by its support: the list of its \(\tau\) positive-mass types, with binary rational masses \(\mu_t>0\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type consists of a partial assignment \(u_t\) and a CO-net \(N_t\). A CO-net specifies, for each attribute \(A\), parents \(\operatorname{Pa}(A)\subseteq X\setminus\{A\}\) and an explicit complete table assigning one optimal value in \(D_A\) to every assignment of its parents.
Define \(\operatorname{FSopt}(u,N)\) as follows. Start with an empty assignment \(s\). Repeatedly select an unassigned attribute \(A\) whose table entries compatible with \(s\) all specify the same value; assign \(u[A]\) if \(A\) is fixed by \(u\), and otherwise assign that common value. Return the complete assignment, or fail if no attribute is eligible before completion. Resolve attribute choices by a fixed input ordering.
Every input net is promised conditionally acyclic: this procedure completes for every partial assignment and every sequence of eligible attribute choices; recognizing this promise is outside the task.
Choose a complete product \(f(t)\supseteq u_t\) for each supported type to maximize \(\sum_{t=1}^{\tau}\mu_t\mathbf{1}[f(t)=\operatorname{FSopt}(u_t,N_t)]\). Let \(L\) be the total binary input length, including domains, tables, partial assignments, and masses; state running times in \(m,\tau,d,L\).
Is this mass-weighted completion optimization problem solvable in polynomial time, or is it NP-hard?
Known discrete result: for a single request, Forward Sweep computes the most preferred completion of any partial assignment when the CO-net induced by a strict total preference order is conditionally acyclic; the procedure is polynomial-time with explicit tables (Gimenez and Mengin, 2023).
The problem is polynomial-time solvable, and its maximum objective value is always \(1\). The decisive feature is that each supported type receives its own independently chosen completion.
For each type \(t\), define \(g_t=\operatorname{FSopt}(u_t,N_t)\), using the prescribed attribute ordering. The conditional acyclicity promise guarantees that this procedure completes. Moreover, \(g_t\) extends \(u_t\): whenever an attribute fixed by \(u_t\) is selected, the procedure assigns precisely its prescribed value. Every other assignment uses a value from the attribute’s domain. Thus \(g_t\) is a feasible complete product for type \(t\).
Choose \(f(t)=g_t\) for every supported type. Every indicator in the objective then equals \(1\), so the resulting objective value is \(\sum_{t=1}^{\tau}\mu_t=1\). Conversely, for any feasible choices, each indicator is at most \(1\); since all masses are positive and sum to \(1\), the objective is at most \(1\). This proves optimality.
To justify polynomial running time directly, consider one eligibility test for an unassigned attribute \(A\). Scan its explicitly listed table. A row is compatible with the current assignment \(s\) exactly when it agrees with \(s\) on every already assigned parent. Among compatible rows, retain the first optimal value encountered and check whether every other compatible row specifies that same value.
There is always at least one compatible row: \(s\) restricts only some parents, all parent domains are nonempty, and the table contains every parent assignment. Consequently, this scan implements exactly the eligibility condition in the question.
For each supported type, repeat the following at most \(m\) times:
The promise guarantees an eligible attribute whenever the assignment is incomplete. Hence this algorithm computes every \(g_t\) and returns the optimal mapping \(f\).
For an explicit conservative complexity bound, each type has at most \(L\) table rows, each containing at most \(m\) parent values. Each sweep stage scans each attribute’s table at most once. Across all types, there are therefore at most \(O(\tau m^2L)\) parent-value checks. Even allowing \(O(L)\) bit operations for each check, lookup, or value comparison, the entire computation takes \(O(\tau m^2L^2)\) bit operations, including straightforward parsing and output. This bound is polynomial in the stated input parameters. The dependence on \(d\) is already included in \(L\), because domains and tables are explicitly listed; no enumeration of the complete-product space is needed. The masses require no optimization arithmetic, since the constructed solution satisfies every supported type.
The supplied discrete preference theorem is not needed here: the completion promise and the stated definition of \(\operatorname{FSopt}\) suffice.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time solvability and optimal objective value \(1\). The only issue is a minor edge case in the stated running-time bound when \(m=0\).
The prover defines \(g_t=\operatorname{FSopt}(u_t,N_t)\) using the required ordering. The input promise applies to every partial assignment and every sequence of eligible choices, so it guarantees completion for this particular execution. No preference-representation theorem is needed.
Each attribute is assigned exactly once. Whenever an attribute is fixed by \(u_t\), the procedure assigns its prescribed value. Otherwise, it assigns a table value belonging to the attribute’s domain. Consequently, \(g_t\) is complete and extends \(u_t\). This reasoning is correct under the task’s definition of a partial assignment.
The task imposes no constraint coupling the completions selected for different types. Therefore, choosing \(f(t)=g_t\) for every supported type is feasible. Every objective indicator equals \(1\), giving objective value \(\sum_{t=1}^{\tau}\mu_t=1\). This calculation is correct.
Every indicator is at most \(1\), and all masses are positive and sum to \(1\). Thus every feasible solution has objective value at most \(1\). Together with the construction, this proves optimality.
Checking a table row against the values of its already assigned parents implements compatibility with \(s\) exactly. Comparing the optimal values across all compatible rows implements the stated eligibility condition. At least one compatible row exists because the parent domains are nonempty and the table contains every parent assignment. This also covers attributes with no parents.
Scanning unassigned attributes in the prescribed ordering and selecting the first eligible attribute respects the specified tie-breaking rule. Each successful stage assigns one new attribute, so there are at most \(m\) stages. The promise rules out failure at an incomplete stage.
With explicit tables, the number of rows for any type is bounded by \(L\). Each row requires at most \(m\) parent-value checks, and a stage scans each attribute’s table at most once. Summing over at most \(m\) stages and \(\tau\) types gives the stated conservative bound of \(O(\tau m^2L)\) parent-value checks. Allowing \(O(L)\) bit operations per check or comparison yields \(O(\tau m^2L^2)\). For \(m\geq 1\), this also accommodates straightforward parsing and output. Explicit domain and table encodings account for the dependence on \(d\).
Minor — zero-attribute running time. The task does not explicitly exclude \(m=0\). In that case, the correctness argument still applies, but the displayed bound \(O(\tau m^2L^2)\) vanishes and cannot include parsing a nonempty input, as claimed.
The minimum clarification is to state that this bound assumes \(m\geq 1\) and separately account for the \(m=0\) case. This is a routine boundary correction and does not affect the complexity classification.
There are no blocking issues, unjustified theorem applications, or substantive mathematical gaps.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.