Abstract The analysis problem for a given Algorithm-Based Fault Tolerant (ABFT) system involves determining two important performance measures of the system, namely, its error-detectability and its fault-detectability. Our results clearly delineate the computationally intractable and the efficiently solvable versions of the analysis problem. Specifically, we show that the problems of determining the error-detectability and the fault-detectablity of a given system are, in general, Co-NP-complete and hence unlikely to be efficiently solvable. We also present efficient algorithms for several restricted versions of these problems. In addition, we present a new branch-and-bound algorithm to determine the error-detectability of a system. This algorithm, which runs in O(( g − 1) l ) time where g is the maximum number of data items included in a test (check) and l is the number of tests, is suitable for systems with a small value of l.