Open question · OPEN-DS-TILT-DUAL-EXACT-COMPLEXITY

What is the exact bit complexity of tilt optimization?

Openpublication: openno direct precedent foundparked

Meaning

Resolve remaining exact-complexity questions as nuisance dimension and cell count vary.

Scientific context

For the profiled criterion, exact minimization of the tilt dual is polynomial in bit complexity when there is a single nuisance parameter, for every cell count, and polynomial in arithmetic operations for any fixed nuisance dimension. What remains open is a polynomial bit bound for a fixed nuisance dimension of two or more with a variable cell count, and any exact statement — or hardness obstruction — when the nuisance dimension itself varies. Generic parametric-search lower bounds do not automatically transfer to this particular grouping problem, which is why the question is not already answered by the general theory.

Statement

Determine whether min_beta v_K(S_psi-beta S_lambda), with K and d_lambda part of the rational input, admits exact algebraic optimization in polynomial bit complexity using the fixed-tilt interval-DP oracle, including active tie refinements, without materializing a potentially large parametric-DP envelope. Settled by DS-TILT-DUAL-CERTIFICATE and its audit: fixed-tilt exact evaluation, polynomial certified-epsilon minimization, exact polynomial-bit minimization at d_lambda=1 for every K (root-separation bisection), and exact minimization in polynomially many arithmetic operations for fixed d_lambda>=2 with variable K (Toledo 1993 fixed-dimension parametric search with degree-2 comparisons). Remaining: a polynomial bit bound for fixed d_lambda>=2 with variable K (a root-separation argument for the conic breakpoint arrangement carried through the parametric search), and any exact statement, or hardness obstruction, for variable d_lambda.

Assumptions

positive rational weights; exact-K nonempty cells; rational score table
exact means an algebraic optimizer/value with checkable comparisons, not a crossings grid or epsilon approximation
common empirical nuisance-null directions may be quotiented before optimization
the d_lambda=1 case is closed by AUDIT-DS-PRACTICAL-CERTIFIED-SOLVER section 7.5; the fixed-d_lambda arithmetic bound is prior art (Toledo 1993), not a bit bound

Ruled out by

General parametric-shortest-path envelope lower bounds do not automatically transfer to the special scalar grouping DP, and Megiddo/Toledo parametric search shows the envelope need not be materialized. A valid hardness reduction for variable d_lambda, or a bit-complexity analysis of fixed-dimension parametric search, is required.

Closest prior work

Relationships

Evidence references

Reviewed inputs and supporting evidence; these are not proof prerequisites.

Publication-grade audit of the DS19 tilt-DP certificate complexAUDIT-DS-PRACTICAL-CERTIFIED-SOLVER

Related settled results

Scalar-POI tilt-DP gives a valid two-sided certificate with an exact saddle closure gateDS-TILT-DUAL-CERTIFICATE

The full chain beneath it

Where it comes from

Raised by

Local graph

Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

The question in full

Exact bit complexity of the tilt-DP dual

For positive rational weights and a rational score table, with $K$ and $d_\lambda$ in the input, does $\min_\beta\hat v_K(S_\psi-\beta S_\lambda)$ admit exact optimization in polynomial bit complexity with the fixed-tilt interval-DP oracle, without materializing the parametric-DP envelope? DS19 proves exact fixed-tilt evaluation, polynomial certified- $\varepsilon$ minimization, exact polynomial-bit minimization at $d_\lambda=1$ , and polynomially many arithmetic operations for fixed $d_\lambda\ge2$ . Remaining: a polynomial bit bound for fixed $d_\lambda\ge2$ and any statement for variable $d_\lambda$ . Target claim: OPEN-DS-TILT-DUAL-EXACT-COMPLEXITY; parked study a work record.

From OPEN_PROBLEMS.md