With what Frequency are Apparently Intractable Problems Difficult?
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...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148954 |
| Summary: | 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. |
|---|