New answers tagged

6

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 optimizable in polynomial time. On the other hand, the natural polytope $P$ given in the post still suffices to solve Horn-SAT via linear programming, as the solution to ...


2

Proposition 4.1 of https://arxiv.org/abs/2004.02375 states that for sufficiently large $n$, if $s$ has length less than $(1+e^{-600})n^2/e$ then $\#_n(s)\le \exp(e^{-600}n)n!$. (note that here they respectively use $k,n$ in place of $n,c_n$) Thus even if $c_n$ grows quadratically but with a small constant, any $s$ with length $c_n$ will have an exponentially ...


4

PSPACE-completeness As suggested by Tim here, the problem can be shown to be PSPACE-hard by reduction from the Corridor Tiling Problem: Instance: a finite set of Wang tiles $\mathcal{T}=\{T_1,\ldots,T_h\}$, a special Wang tile $T_0$, and a width $n\in\mathbb{N}$ given in unary notation. Question: is there any height $m\in\mathbb{N}$ such that an $n\times m$ ...


Top 50 recent answers are included