Agrawal, M. ; Biswas, S. (1993) Polynomial isomorphism of 1-L-complete sets Proceedings of IEEE the Eighth Annual Structure in Complexity Theory Conference, 1993 . pp. 75-80.
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...
Related URL: http://dx.doi.org/10.1109/SCT.1993.336539
Abstract
Let C be any complexity class closed under log-lin reductions. It is shown that all complete sets for C under 1-L reductions are polynomial time isomorphic to one other. It is indicated how to generalize the result to reductions computed by finite-crossing machines.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to IEEE. |
| ID Code: | 95355 |
| Deposited On: | 07 Nov 2012 04:41 |
| Last Modified: | 07 Nov 2012 04:43 |
Repository Staff Only: item control page
