ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let (P)({\cal P}) be a properly posed problem, and let Sc+{\cal S}^+_c denote the positive canonical dual feasible set; write int⁡Sc+\operatorname{int}{\cal S}^+_c for its interior. Criterion of NP-hardness. The problem (P)({\cal P}) is NP-hard if and only if

int⁡Sc+=∅.\operatorname{int}{\cal S}^+_c=\emptyset.

This conjecture connects the computational difficulty of the nonconvex problem with the geometry of its canonical dual feasible set. The supplied text attributes the proposal to Gao and collaborators, but gives no resolution, so its status remains open.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.