New answers tagged co.combinatorics
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