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 |
| _version_ | 1826211907540877312 |
|---|---|
| author | Meyer, A.R. Paterson, M.S. |
| author_facet | Meyer, A.R. Paterson, M.S. |
| author_sort | Meyer, A.R. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:13:20Z |
| id | mit-1721.1/148954 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:13:20Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489542023-03-30T03:16:32Z With what Frequency are Apparently Intractable Problems Difficult? Meyer, A.R. Paterson, M.S. 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. 2023-03-29T14:12:28Z 2023-03-29T14:12:28Z 1979-02 https://hdl.handle.net/1721.1/148954 5185137 MIT-LCS-TM-126 application/pdf |
| spellingShingle | Meyer, A.R. Paterson, M.S. With what Frequency are Apparently Intractable Problems Difficult? |
| title | With what Frequency are Apparently Intractable Problems Difficult? |
| title_full | With what Frequency are Apparently Intractable Problems Difficult? |
| title_fullStr | With what Frequency are Apparently Intractable Problems Difficult? |
| title_full_unstemmed | With what Frequency are Apparently Intractable Problems Difficult? |
| title_short | With what Frequency are Apparently Intractable Problems Difficult? |
| title_sort | with what frequency are apparently intractable problems difficult |
| url | https://hdl.handle.net/1721.1/148954 |
| work_keys_str_mv | AT meyerar withwhatfrequencyareapparentlyintractableproblemsdifficult AT patersonms withwhatfrequencyareapparentlyintractableproblemsdifficult |