Completeness of path-problems via logical reductions

DOI10.1006/inco.1995.1127zbMath0832.68048OpenAlexW2038622357MaRDI QIDQ1898118

Iain A. Stewart

Publication date: 20 September 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1995.1127

zbMATH Keywords

complexity classquantifier-free projections

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Generalized hex and logical characterizations of polynomial space ⋮ Dichotomies for classes of homomorphism problems involving unary functions ⋮ A note on first-order projections and games. ⋮ Positive versions of polynomial time

This page was built for publication: Completeness of path-problems via logical reductions