d4-journals-ai-2011-0074 (d4-journals-ai-2011-0074)

Given a finite tuple set \(X\) and a society represented by \(\tau\) complete user types \(\theta=(R_\theta,C_\theta)\) with rational masses \(\mu_\theta\), where each \(R_\theta\) is a finite strict partial order and \(C_\theta\subseteq R_\theta\), compute the prefix contraction \(P^-_\theta\) for every type and the retained-comparison frequencies \(\rho(x,y)=\sum_{\theta:(x,y)\in R_\theta\setminus P^-_\theta}\mu_\theta\) for \((x,y)\in X\times X\).

Let \(X\) be a finite tuple set with \(m=|X|\). A society is given by its support: a list of \(\tau\) distinct types \(\theta=(R_\theta,C_\theta)\) with positive binary rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Each \(R_\theta\subseteq X\times X\) is a strict partial order and \(C_\theta\subseteq R_\theta\); both are given explicitly as lists of pairs, and either may be empty. Let \(L\) be the total binary input length.
A contraction of \(R\) by \(C\) is a set \(P^-\) with \(C\subseteq P^-\subseteq R\) such that \(R\setminus P^-\) is a strict partial order. It is prefix if every edge in \(P^-\) is the first edge of an \(R\)-path whose endpoint pair belongs to \(C\) and whose only edge in \(P^-\) is that first edge; paths of one edge are allowed.
The required outputs are the prefix contraction \(P^-_\theta\) for each supported type and the exact rational frequencies \(\rho(x,y)=\sum_{\theta:(x,y)\in R_\theta\setminus P^-_\theta}\mu_\theta\) for every \((x,y)\in X\times X\).

Is this computation solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

For explicit finite relations, the prefix contraction exists uniquely, and an algorithm computes it in \(\mathcal{O}(|C|^2|R|\log|R|)\) time. This result concerns individual finite relations; it does not state a complexity classification for the rational-mass society problem.

Conclusion

The computation is polynomial-time solvable in \(m,\tau,L\). The supplied theorem computes each supported type’s unique prefix contraction, and the exact rational frequencies can then be accumulated with polynomially bounded integer arithmetic.

1. Computing the supported contractions

For each supported type \(\theta\), write \(r_\theta=|R_\theta|\) and \(c_\theta=|C_\theta|\). The hypotheses of the supplied individual-relation theorem hold: \(R_\theta\) is an explicitly represented finite strict partial order, and \(C_\theta\subseteq R_\theta\).

If \(C_\theta=\varnothing\), its unique prefix contraction is \(P^-_\theta=\varnothing\). Indeed, this is a contraction because the retained relation is \(R_\theta\). Conversely, any edge in a nonempty prefix contraction would require a witnessing path whose endpoint pair belongs to \(C_\theta\), which is impossible.

For every type with nonempty \(C_\theta\), apply the supplied algorithm. Using \(\log(2+r_\theta)\) to accommodate small relations, its running time is bounded by

\(\mathcal{O}\!\left(c_\theta^2r_\theta\log(2+r_\theta)\right)\).

Since \(c_\theta\leq r_\theta\leq m^2\), summing over the explicitly listed support gives a bound of

\(\mathcal{O}\!\left(\tau m^6\log(2+m)\right)\)

for these relation computations, apart from polynomial input-processing costs. Elements of \(X\) can be indexed by integers from \(1\) through \(m\), so manipulating relation endpoints also has polynomial bit cost.

Crucially, this algorithm processes exactly the \(\tau\) listed types. It never enumerates possible unsupported types.

2. A polynomial-size common denominator

Write each input mass as \(\mu_\theta=a_\theta/b_\theta\), where \(a_\theta,b_\theta\) are positive binary integers. They need not initially be relatively prime.

Define the integer common denominator and weights by

\(D=\prod_\theta b_\theta,\qquad A_\theta=a_\theta(D/b_\theta).\)

Each division is exact. Moreover,

\(\sum_\theta A_\theta=D\sum_\theta\mu_\theta=D.\)

Let \(\ell(b_\theta)\) denote the binary encoding length of \(b_\theta\). Because all mass encodings are part of the input,

\(\sum_\theta\ell(b_\theta)\leq L.\)

Consequently,

\(\log_2D=\sum_\theta\log_2b_\theta\leq L,\)

so \(D\) has at most \(L+1\) bits. Positivity and the identity \(\sum_\theta A_\theta=D\) imply \(0<A_\theta\leq D\); thus every integer weight also has at most \(L+1\) bits.

Computing \(D\) by successive multiplication, and then computing the \(A_\theta\) by exact division and multiplication, therefore takes polynomial bit time. Every intermediate product is bounded by \(D\), since all factors are positive integers.

3. Computing every frequency exactly

Initialize an integer \(N(x,y)=0\) for each \((x,y)\in X\times X\). For every supported type \(\theta\), enumerate its retained edges \(R_\theta\setminus P^-_\theta\), adding \(A_\theta\) to \(N(x,y)\) for each retained edge \((x,y)\).

By construction,

\(N(x,y)=\sum_{\theta:\,(x,y)\in R_\theta\setminus P^-_\theta}A_\theta.\)

Therefore the exact required frequency is

\(\rho(x,y)=N(x,y)/D.\)

Every numerator, including every intermediate accumulator, satisfies \(0\leq N(x,y)\leq\sum_\theta A_\theta=D\). Hence all additions involve integers of at most \(L+1\) bits. There are at most \(\tau m^2\) additions and \(m^2\) output entries.

If reduced fractions are desired, compute \(g(x,y)=\gcd(N(x,y),D)\) and output numerator \(N(x,y)/g(x,y)\) and denominator \(D/g(x,y)\). Integer greatest-common-divisor computation has polynomial bit complexity. For a zero numerator this produces \(0/1\), since \(\gcd(0,D)=D\).

Thus the frequencies have total encoding length \(\mathcal{O}(m^2(L+1))\), apart from pair labels, and can all be produced in polynomial time.

4. Classification

Each contraction is correct by the supplied theorem, including the directly handled empty cases. The integer accumulation gives exactly the specified frequencies, and both arithmetic bit lengths and output size are polynomially bounded. Together, these facts prove the requested polynomial-time classification for the explicitly supported rational-mass society.

⟨structured verdict parsed — rendered above⟩

Verification report

Result: proved. The argument establishes polynomial-time solvability for the explicitly supported rational-mass society. No major or minor mathematical issues were found.

1. Applicability of the supplied theorem

The prover correctly uses the individual-relation result supplied in USER_TASK. Each supported type has an explicitly represented finite strict partial order \(R_\theta\) and a subset \(C_\theta\subseteq R_\theta\), exactly as required by that result.

The theorem supplies existence, uniqueness, and an algorithm for the required prefix contraction. Applying it separately to the \(\tau\) listed types does not require enumerating unsupported types.

2. Empty contraction sets and small relations

The case \(C_\theta=\varnothing\) is handled correctly:

• \(P^-_\theta=\varnothing\) satisfies the contraction conditions because the retained relation is \(R_\theta\).
• Any nonempty prefix contraction would contain an edge requiring a witnessing path with endpoint pair in \(C_\theta\), which is impossible.

This also covers \(R_\theta=\varnothing\), since \(C_\theta\subseteq R_\theta\).

Replacing the logarithmic factor by \(\log(2+r_\theta)\) appropriately accommodates small relation sizes without changing the polynomial classification.

3. Total cost of the relation computations

The bounds \(c_\theta\leq r_\theta\leq m^2\) are valid. Consequently, the stated total bound
\[ \mathcal{O}\!\left(\tau m^6\log(2+m)\right) \]
is a valid coarse upper bound for the supplied relation algorithms.

The observation about indexing elements of \(X\) correctly addresses endpoint representation: endpoint manipulation and input processing add only polynomial bit costs. The explicitly listed contractions also have polynomial total output size, since each is a subset of its input relation.

4. Common denominator and integer weights

The definitions
\[ D=\prod_\theta b_\theta,\qquad A_\theta=a_\theta(D/b_\theta) \]
are valid, and every indicated division is exact. Normalization gives
\[ \sum_\theta A_\theta=D. \]

The denominator-length calculation is correct:
\[ \log_2D=\sum_\theta\log_2b_\theta \leq\sum_\theta\ell(b_\theta)\leq L. \]
Thus \(D\) has at most \(L+1\) bits. Positivity and normalization imply \(0<A_\theta\leq D\), so the same bound holds for the weights.

The claim about bounded intermediate products is valid for the described computations: partial denominator products are bounded by \(D\), and the final weight products are bounded by \(D\). Standard binary integer multiplication and exact division therefore suffice in polynomial bit time. Reduced input fractions are unnecessary.

5. Exact frequency accumulation and output size

For each pair, the accumulator sums precisely the weights of the supported types retaining that pair. Dividing by \(D\) therefore gives exactly the required frequency.

The bound \(0\leq N(x,y)\leq D\) holds for final and intermediate accumulators because all weights are positive and their total is \(D\). At most \(\tau m^2\) additions are required, each involving integers of polynomial bit length.

Fraction reduction is optional and correctly described. Polynomial-time greatest-common-divisor computation applies to the bounded integers, including zero numerators, for which the output is \(0/1\).

The total frequency encoding bound \(\mathcal{O}(m^2(L+1))\), apart from pair labels, is valid.

6. Assignment resolution

The prover supplies both required outputs and accounts for relation computation, exact arithmetic, and output size. Its polynomial-time claim follows from the argument as written. No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩