On Relationships Between Approximate and Probabilistic Complexity Classes  

作　　者：李祥 李广元 

机构地区：[1]Institute of Computer Science,Guizhou University.Guiyany 550025,PRC and State Key Laboratory of Information Security,Graduate School,Academia Sinica,Beijiny 100039,PRC,Institute of Computer Science,Guizhou University.Guiyany 550025,PRC and State Key Laboratory of Information Security,Graduate School,Academia Sinica,Beijiny 100039,PRC

出　　处：《Science China Mathematics》1994年第2期247-256,共10页中国科学：数学（英文版）

基　　金：Project supported by the NSF Grant of China;Guizhou Science Foundation

摘　　要：This paper introduces "almost correct" and "almost fast" exponential-time approximation algorithms,and studies relationships between the approximate and probabilistic complexity classes.Some re-sulis on incomparability between these classes have been obtained.This paper introduces 'almost correct' and 'almost fast' exponential-time approximation algorithms,and studies relationships between the approximate and probabilistic complexity classes.Some re-sulis on incomparability between these classes have been obtained.

关 键 词：APPROXIMATE ALGORITHM PROBABILISTIC ALGORITHM RELATIVIZATION COMPLEXITY CLASSES APPROXIMATE CLASSES incomparability of COMPLEXITY CLASSES 

分 类 号：O241[理学—计算数学]