For a bi-infinite zero-one matrix, ask whether one uniform bound exists such that each column either contains fewer than 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.
Articles by others on the same topic
There are currently no matching articles.