Partitioning of Polynomial Tasks: Test Generation, an Example

The objective of this paper is to analyze the circumstances under which a partitioning of a task with a polynomial complexity will result in an overall reduction of its execution time. 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 of 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.