Open question · OPEN-D-PARAMETERIZED-COMPLEXITY

Can exact D search improve beyond XP?

Openpublication: open

Meaning

Resolve the parameterized complexity of global finite quantization in dimension and bin count.

Scientific context

Whether the polynomial exponent in the arrangement-enumeration algorithm (D-GLOBAL-XP) is tight, and where the NP-hardness and fixed-parameter-tractability boundaries for the finite determinant problem actually lie, is open. Any answer needs to come with a valid complexity reduction rather than an analogy to a superficially similar problem.

Statement

Determine NP-hardness/FPT/W[1]/ETH boundaries and tightness of N^{O(Kd)}; valid reductions are required.

Relationships

Related settled results

Exact finite D optimization is XP for fixed (d,K)D-GLOBAL-XP

The full chain beneath it

Where it comes from

Raised by

Exact finite D optimization is XP for fixed (d,K)D-GLOBAL-XP

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

Parameterized complexity

NP-hardness for fixed $d=2$ and variable $K$ ; for $K=d+1$ and variable $d$ ; FPT in $K+d$ ; W[1]/ETH bounds; tightness of the $N^{O(Kd)}$ exact route. No imported k-means or subset-selection hardness without a valid reduction.

From OPEN_PROBLEMS.md