Methods for proving completeness via logical reductions (Q685391): Difference between revisions

We illustrate five different techniques for showing that problems are complete for some complexity class via projection translations (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 devison problems are equated with sets of strings instead of sets of finite structures.