Hardness conjecture for maximizing polytope sections, projections, and halfspace sections
Statement
Let be a polytope, let be a face dimension, and let be a hyperplane. For a central hyperplane , write for one of the associated halfspaces.
Hardness conjecture. (i) It is -hard to find a hyperplane which maximizes the number of -dimensional faces of . (ii) It is -hard to find a hyperplane which maximizes the volume of the orthogonal projection of onto . (iii) It is -hard to find a central hyperplane which maximizes the volume of the halfspace section .
The paper first establishes related -hardness results for weighted edge sections and vertex halfspace sections, and then proposes these stronger unweighted and general-dimensional claims. The projection claim is motivated by the hardness of computing zonotope volumes, which implies hardness for volumes of projections of polytopes; the conjectured resolutions of the displayed claims are not supplied in the source.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.