The complexity of TRMCS-like spiral specification

Modern software is often constructed using “spiral specification”; i.e. the specification is a dynamic document that is altered by experience with the current version of the system. Mathematically, many of the sub-tasks within spiral specification belong to the NP-complete class of tasks. In the traditional view of computer science, such tasks are fundamentally intractable and only solvable using incomplete, approximate methods that can be undependable. This traditional view suggests that we should routinely expect spiral specification to always be performed very poorly. This paper is an antidote to such pessimism. Contrary to the traditional view, we can expect that spiral specification can usually be performed adequately, providing that analysts augment their current tools with random probing