Finite-column decision problem
= Finite-column decision problem
For a bi-infinite zero-one matrix, ask whether one uniform bound $D$ exists such that each column either contains fewer than $D$ ones or contains infinitely many ones in both directions. This decision problem has <Solvability complexity index> three even for general algorithms and is a standard source of lower bounds by reduction.