摘要
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.
基金
Project supported by the NSF Grant of China
Guizhou Science Foundation
