METHODS FOR PROVING COMPLETENESS VIA LOGICAL REDUCTIONS

Authors
STEWART IA
Citation
Ia. Stewart, METHODS FOR PROVING COMPLETENESS VIA LOGICAL REDUCTIONS, Theoretical computer science, 118(2), 1993, pp. 193-229
Citations number
32
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
118
Issue
2
Year of publication
1993
Pages
193 - 229
Database
ISI
SICI code
0304-3975(1993)118:2<193:MFPCVL>2.0.ZU;2-W
Abstract
In this paper we illustrate five different techniques for showing that problems are complete for some complexity class via projection transl ations (these are extremely weak logical reductions). These techniques would not be available to us if we were to take the traditional view of complexity theory where decision problems are equated with sets of strings instead of sets of finite structures.