Mangara
  • Member for 8 years
  • Last seen more than 1 year ago
Is it decidable to determine if a given shape can tile the plane?
Accepted answer
23 votes

According to the introduction of [1], The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes [4]. [1] ...

View answer
Obituaries of dead conjectures
19 votes

The $\mathsf{3SUM}$-conjecture: That any deterministic algorithm for $\mathsf{3SUM}$ requires $\Omega(n^2)$ time. This was disproven in 2014, by Allan Grønlund and Seth Pettie, who gave a ...

View answer
SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms
5 votes

The paper SAT Encodings of the At-Most- k Constraint, by Alan M. Frisch and Paul A. Giannaros compares five different encodings of the at-most-k constraint, both theoretically and by running ...

View answer