# Tag Info

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 ...
• 10.8k
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 ...
• 5,772

### 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 ...

### 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$ ...
• 18.2k
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 ...
• 1,469
Accepted

• 18.2k