|
|||||
|
|
A note on complete sets and transitive closure |
|
| Authors: | Ronald V. Book Celia Wrathall |
| Affiliation: | (1) Department of Mathematics, University of California at Santa Barbara, Santa Barbara, California, USA |
| Abstract: | It is shown that there is a length-preserving relation that is NP-complete such that the transitive closure of the relation is PSPACE-complete.This research was supported in part by the National Science Foundation under Grant MCS80-11979. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |