Polynomial isomorphism of 1-L-complete sets

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


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