# Tag Info

Accepted

### minimum number of 2d elements whose sums across both dimensions satisfy some threshold

Your problem is NP-hard, by reduction from the equal-cardinality partition problem. Let $a_1,\dots,a_n$ be an instance of the equal-cardinality partition problem (so $n$ is even). The reduction works ...
Accepted

### Can the optimization version of a problem be NP-hard while its decision version is in P?

Lastly, I did not use the set $𝐶$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation. It is not correct, indeed :) You are describing a decision problem, ...

### Can the optimization version of a problem be NP-hard while its decision version is in P?

Often, if the decision problem can be solved in polynomial time, the optimization problem can be solved in polynomial time as well. For example, if you could decide in polynomial time if a problem has ...
1 vote

### Which algorithms could be suitable for solving my disjunctive programming problem?

The prior answer already explained a standard way to solve this kind of problem: introduce boolean (0-or-1) variables to model the disjunction, and then solve with an off-the-shelf integer linear ...
1 vote
Accepted

### Integrality gap and complexity classes

The question is incorrect. The integrality gap is defined for a linear programming formulation of the problem and not fundamentally for the problem. It is possible that a problem has more than one ...
1 vote

### Boolean constraints for a connected component of a graph

Here is one encoding. Introduce boolean variables $x_{v,i}$, with the intended meaning that $x_{v,i}$ is true if $v$ is selected and $v$ can by reached by a path of length $\le i$ from $s$ (where $s$ ...
1 vote
Accepted

### Possible to solve a combinatorial game with integer programming?

I believe you can't, for many/most combinatorial games. In particular, I believe optimal play for two-player combinatorial games is often a PSPACE-complete problem (sometimes a EXP-complete problem), ...

Only top scored, non community-wiki answers of a minimum length are eligible