Skip to main content
7 votes
Accepted

Does Horn SAT (Horn formula in CNF) have an integral polytope?

EDIT: Strengthened Theorem 2. The answer to the problem as posed is no, unless P=NP: Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is ...
Neal Young's user avatar
  • 10.8k
6 votes
Accepted

Complexity of Finding Largest Set of Intersecting Convex Polytopes

Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets. Let $h_1,\ldots,h_p$ denote the ...
Gamow's user avatar
  • 5,772
6 votes

Reaching the double exponential upper bound in Fourier-Motzkin elimination

I think this upper bound is tight. As an example, consider the following system \begin{align*} +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le ...
Sasha Kozachinskiy's user avatar
5 votes

Decide whether a point is a vertex of a polytope?

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ ...
Sasho Nikolov's user avatar
4 votes
Accepted

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope. First, recall the circulation polytope of a graph on the bottom of page 4 of Generating ...
Elle Najt's user avatar
  • 1,469
3 votes
Accepted

Properties of convex polytope of 0-1 matrices

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M =...
Andrew Morgan's user avatar
2 votes
Accepted

Hardness of computing the dimension of an integral polytope?

Yes, MORE-SAT, defined below, is one example of a combinatorial optimization problem for which the natural 0/1 integer linear program (ILP) is guaranteed to be feasible, and determining the dimension ...
Neal Young's user avatar
  • 10.8k
2 votes
Accepted

On polytope lattice points

Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints $0\le x_i \le 1$ for all ...
Sasho Nikolov's user avatar
2 votes
Accepted

Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

To my knowledge, Seidel's construction has only been published in O'Rourke's book and nowhere else. In one of his papers, Seidel even refers to O'Rourke's book for a description of his own ...
Gamow's user avatar
  • 5,772

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