Partitioning of polynomial tasks: test generation, an example

The circumstances under which a partitioning of a task with a polynomial complexity will result in an overall reduction of its execution time are analyzed. It is assumed that the task executor is sequential in nature, namely it can execute only one task at a time. Since partitioning of a task into smaller subtasks will, most probably, result in subtask overlap, there is a risk that a given partitioning scheme will yield an increase in its overall execution time. Formulas are derived to test the effectiveness of any proposed partitioning scheme. In the case of multiple partitioning options, the best one can be easily obtained. One of the possible tasks that this analysis is applicable to is the test generation of digital circuits with a uniprocessor