QUASI-INJECTIVE REDUCTIONS

被引：3
作者：
HEMASPAANDRA, E
HEMASPAANDRA, LA
机构：
[1] UNIV ROCHESTER,DEPT COMP SCI,COMP SCI BLDG 620,ROCHESTER,NY 14627
[2] LE MOYNE COLL,SYRACUSE,NY 13214
来源：
THEORETICAL COMPUTER SCIENCE | 1994年 / 123卷 / 02期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0304-3975(94)90137-6
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A reduction is said to be quasi-injective if no element of the range is mapped to by infinitely many elements. Via two natural families of quasi-injective reductions, we study the connection between degree of injectivity and strength of reduction. In particular, we completely determine the relative strengths of polynomial-time f(n)-to-I reductions, and of polynomial-time k-to-k' reductions.
引用
收藏
页码：407 / 413
页数：7
相关论文
共 12 条
[1]   P-PRINTABLE SETS [J].
ALLENDER, EW ;
RUBINSTEIN, RS .
SIAM JOURNAL ON COMPUTING, 1988, 17 (06) :1193-1202
[2]  
AMBOSSPIES K, 1987, 2ND ANN STRUCT COMPL, P60
[3]  
BEIGEL R, 1989, 4TH P STRUCT COMPL T, P216
[4]  
Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023
[5]  
DOWNEY R, 1989, 4TH P STRUCT COMPL T, P3
[6]  
GOLDSMITH J, 1989, 816 U WISC MAD TECH
[7]   COMPLEXITY-MEASURES FOR PUBLIC-KEY CRYPTOSYSTEMS [J].
GROLLMANN, J ;
SELMAN, AL .
SIAM JOURNAL ON COMPUTING, 1988, 17 (02) :309-335
[8]  
Hopcroft J. E., 1979, INTRO AUTOMATA THEOR
[9]  
KURTZ SA, 1990, COMPLEXITY THEORY RESTROSPECTIVE, P108
[10]  
Soare Robert I., 1987, PERSPECTIVES MATH LO
12