- INSTANCE:
A locally testable language
*L*, i.e., a language*L*such that, for some positive integer*j*, whether or not a string*x*is in the language depends on (a) the prefix and suffix of*x*of length*j-1*, and (b) the set of substrings of*x*of length*j*. - SOLUTION:
An order
*j*, i.e., a positive integer*j*witnessing the local testability of*L*. - MEASURE:
The value of the order, i.e.,
*j*.

*Good News:*Admits a PTAS [321].