Methods for proving completeness via logical reductions
type: Item
instance of: scholarly article
title: Methods for proving completeness via logical reductions
zbMATH Open document ID: 0777.68040
DOI: 10.1016/0304-3975(93)90109-7
author: Iain Stewart
published in: Theoretical Computer Science
publication date: 1993-12-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03C13
zbMATH DE Number: 417337
zbMATH Keywords: complete problems
zbMATH Keywords: descriptive complexity theory
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90109-7
OpenAlex ID: W1976534954
cites work: On uniformity within \(NC^ 1\)
cites work: Constant Depth Reducibility
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q3221973
cites work: Q4198056
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q3830533
cites work: Space-bounded reducibility among combinatorial problems
cites work: The subgraph homeomorphism problem
cites work: Symmetric space-bounded computation
cites work: Some Remarks on Generalized Spectra
cites work: Polynomial size \(\Omega\)-branching programs and their computational power
cites work: Maze recognizing automata and nondeterministic tape complexity
cites work: A complexity theory based on Boolean algebra
cites work: Q4016524
cites work: Complete problems for symmetric logspace involving free groups
cites work: Comparing the Expressibility of Languages Formed Using NP-Complete Operators
cites work: Q4694732
cites work: Complete Problems Involving Boolean Labelled Structures and Projection Transactions
cites work: Q4202957
cites work: REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
cites work: Q2757847
cites work: The polynomial-time hierarchy
cites work: Bounded Query Classes
description: scientific article; zbMATH DE number 417337