Feasibility and Unfeasibility of Off-Line Processing.
Marco Cadoli, Francesco M. Donini, Paolo Liberatore, Marco Schaerf · 1996
We formally investigate the idea of processing off-line part of the inputdata in order to speed up on-line computing. In particular, we focus on off-line processing for intractable decision problems. To this end, we define new complexity classes and reductions, and find complete problems. 1 Introduction Motivations. In many cases, the input of a computational problem can be divided into two parts: One, called fixed, is known in advance, while the other one, called variable, comes at the same time as the request of the computation. Such a distinction is interesting when many input instances share the same fixed part. In these cases it makes sense to preprocess off-line the fixed part, putting it into a form such that solving on-line a set of instances becomes easier. This general idea of preprocessing part of the input data has been widely used in many areas of computer science. For example, in computational geometry the techniques for geometric searching (cf. [16, Chap. 2]) use a co...