| paper | d4-conf-ecai-2023-0329 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable, with maximum objective value \(1\); a conservative running-time bound is \(O(\tau m^2L^2)\) bit operations. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
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)]\).
A distribution over exact customer request types, each carrying mass, a partial configuration, and a conditionally acyclic CO-net; choose one complete product per type to maximize the mass receiving its preferred completion. Each user still receives an integral product.
Covers Proposition 2’s preferred-completion result for conditionally acyclic CO-nets; it leaves the other characterization and expressiveness results, and the encoding, decoding, and compression work, outside the mirror.
The strongest honest case is a mass preferential completion problem, anchored by Proposition 2 in Section 4, proved in this paper. For a preference relation \(\succ\) over the product space, the proposition says: if its induced CO-net \(\phi^*_\succ\) is conditionally acyclic, then for every set of attributes \(U\) and partial instantiation \(u\in U\), the most-preferred completion satisfies
\[
\operatorname{opt}(u,\succ)=\operatorname{FSopt}(u,\phi^*_\succ).
\]
This gives a polynomial-time algorithm for the paper’s underlying optimization query on the promised class of CO-nets.
Here is the mirror. Fix a product with finite attribute set \(X\) and finite domains, as in the paper. The input is a distribution over \(\tau\) request types. Type \(t\) has rational mass \(\mu_t>0\), a partial configuration \(u_t\), and a conditionally acyclic CO-net \(N_t\) induced by the users’ underlying strict preference relation. A type is exact for this task: its users share the same preference model and partial configuration. The decision is a recommendation map \(f\), assigning each type a complete product \(f(t)\) extending \(u_t\). Let \(q_t=\operatorname{FSopt}(u_t,N_t)\). The objective is to maximize the mass receiving its preferred completion:
\[
\max_f\ \sum_{t=1}^{\tau}\mu_t\,\mathbf{1}[f(t)=q_t],
\qquad f(t)\supseteq u_t.
\]
A solution is the map \(f\) and its achieved coverage. Each person still receives a complete, integral product; mass describes how many users share the request type.
A plausible regime is a high-volume product configurator serving millions of requests through a relatively small catalogue of saved preference profiles and partial builds. If there are \(N\) requests, with \(n_t\) of type \(t\), then \(\mu_t=n_t/N\). The number of people can be much larger than \(\tau\), and the running time depends on the attribute count, the number of types, and the bit length and size of their CO-net descriptions—not on enumerating the \(N\) people or all possible products. Users who are merely similar would not count as the same type; the regime needs repeated exact profiles and requests.
I expect this mirror to be tractable (Class A): apply Proposition 2 once per support type. Every positive-mass type must receive its \(q_t\) in an optimal solution, so the optimum coverage is \(1\). This is a batch, high-multiplicity form of the paper’s preferred-completion query, and the product domain and per-user objective remain the paper’s. The paper’s introduction explicitly motivates that query with large product configurators, which makes the population scenario plausible.
The case’s soft spot is also its limit: requests do not interact, so the mass changes the population description and coverage measure but not the recommendation for any type. This is a modest continuous mirror, not a new coupled allocation problem. It covers Proposition 2’s CO-net optimization result only; it does not claim to continuize the paper’s learning or compression experiments. Further questions include whether the conditionally acyclic promise can be removed—the paper says recognition is PSPACE-complete, citing Wilson [28]—and what complexity arises when recommendations must satisfy shared inventory constraints or other cross-type coupling.
Proposition 2 is a genuine computational result, so the case against cannot rest on a lack of an algorithmic anchor. Nor is high multiplicity inherently implausible here: a configurator could serve many users with the same saved preference model and partial configuration.
The strongest objection is that the proposed mirror never gives the population a role in the computation. For each type \(t\), the answer is \(q_t=\operatorname{FSopt}(u_t,N_t)\). The coordinates of the recommendation map \(f\) are independent: no constraint links what one type receives to what another receives. The masses \(\mu_t\) describe how common the types are, but do not affect the recommendations. The mirror is therefore a batch of \(\tau\) calls to Proposition 2, not a computational question about a continuous society.
A more substantive version could add shared inventory, a limit on how many recommendation templates the system can offer, or a single recommendation for everyone. Those constraints would make population masses consequential, but they would change the task from finding each user’s preferred completion to allocating scarce options or designing a shared policy. Proposition 2 supplies each type’s ideal completion; it does not model the trade-offs such a system would need to evaluate.
That is a case against spending the programme’s effort on this particular mirror, rather than proof that no worthwhile mirror exists. The mirror is well-posed, and the exact-type scenario is credible. If a batch form of an existing query counts as worthwhile continuization, the proponent’s anchor survives; I cannot honestly make the universal negative airtight.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.