COMPLETENESS OF PATH-PROBLEMS VIA LOGICAL REDUCTIONS

Authors
STEWART IA
Citation
Ia. Stewart, COMPLETENESS OF PATH-PROBLEMS VIA LOGICAL REDUCTIONS, Information and computation, 121(1), 1995, pp. 123-134
Citations number
16
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
121
Issue
1
Year of publication
1995
Pages
123 - 134
Database
ISI
SICI code
0890-5401(1995)121:1<123:COPVLR>2.0.ZU;2-F
Abstract
We show that some well-known path-problems remain complete for the res pective complexity class via quantifier-free projections (these are ex tremely restricted logical reductions). (C) 1995 Academic Press. Inc.