With what Frequency are Apparently Intractable Problems Difficult?
Author(s)
Meyer, A.R.; Paterson, M.S.
DownloadMIT-LCS-TM-126.pdf (2.379Mb)
Metadata
Show full item recordAbstract
An algorithm is almost polynomial-time (apt) iff there is a polynomial p such that for all n, the algorithm halts within p(n) steps on all by at most p(n) inputs of size at most n. It is nown that for NP-complete and polynomial space-complete problems, as well as certain other apparently intractable problems such as integer factoring, the following conditions are equivalent: (1) the problem is solveable by an apt algorithm, (2) the problem (or its complement) is polynomial-time transformable to a polynomial-sparse set, (3) the problem is solvable in polynomial time.
Date issued
1979-02Series/Report no.
MIT-LCS-TM-126