Methods for proving completeness via logical reductions (Q685391)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Methods for proving completeness via logical reductions |
scientific article; zbMATH DE number 417337
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Methods for proving completeness via logical reductions |
scientific article; zbMATH DE number 417337 |
Statements
Methods for proving completeness via logical reductions (English)
0 references
20 December 1993
0 references
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.
0 references
complete problems
0 references
descriptive complexity theory
0 references
0.8102332949638367
0 references
0.8094484806060791
0 references
0.8012567758560181
0 references
0.7894110679626465
0 references
