# Tag Info

Accepted

### Checking equivalence of two polytopes

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in ...
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 ...

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

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

### Checking equivalence of two polytopes

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine ...
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 ...