The subject of this paper is the computational complexity of the deadlock prediction problem for resource allocation. This problem is the question “Is deadlock avoidable?” i.e. “Is there a feasible sequence in which to allocate all the resource requests?” given the current status of a resource allocation system. This status is defined by (1) the resource vector held by the banker, i.e. the quantity of resources presently available for allocation, and (2) the resource requests of the processes: Each process is required to make a termination request of the form “Give me resource vector y and I will eventually terminate and return resource vector z.” Also, each process can make any number of partial requests of the form “If you can’t give me y, then give me a smaller resource vector $y'$ and I will be able to reach a point at which I can halt and temporarily return to $z'$, although I will still need need $y - y' + z'$ to terminate.” If (1) the resources are reusable and (2) partial requests are not allowed, then Habermann’s well known “banker’s algorithm” solves the deadlock prediction problem in polynomial time. The results of this paper are as follows: If either constraint (1) or constraint (2) is removed, then the deadlock prediction problem is NP-complete. A generalization of the banker’s algorithm solves this problem with the following constraint: For each process, the 0 vector and the profitability vectors $(z - y)$ of its partial and termination requests are linearly ordered with respect to size. This case includes systems with one type of resource or with Hansen’s (1973) hierarchically partitioned reusable resources.

A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in the limit if, after some finite point in the sequence, all the guesses are correct and the same (in case there is more than one correct answer). Functions, sets, and functionals which are decidable by such infinite algorithms will be called limiting recursive . These, together with classes of objects which can be identified in the limit , are the subjects of this report. Without qualification, set will mean set of numbers; function will mean number-theoretic function of 1 variable, possibly partial; functionals will take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional, x will invariably stand for a numerical variable; φ for a function variable; g for a guess (a number); n for the numerical variable which indexes the guesses, referred to as the time .