Feasibility and Unfeasibility of Off-line Processing

Proceedings of the Fourth Israeli Symposium on Theory of Computing and Systems (ISTCS'96)

We formally investigate the idea of processing off-line part of the input data 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.

 @inproceedings{cado-etal-96,
 title = {Feasibility and Unfeasibility of Off-line Processing},
 year = {1996},
 author = {Cadoli, Marco and Donini, Francesco M. and Liberatore, Paolo and
 Schaerf, Marco},
 booktitle = {Proceedings of the Fourth Israeli Symposium on Theory of Computing
 and Systems (ISTCS'96)},
 pages = {100-109},
 publisher = {IEEE Computer Society},
 }