On Reducibility Among Combinatorial Problems
A large class of combinatorial problems have been shown by Cook and Karp to be computationally equivalent to within a polynomial. We exhibit some new problems in this class, and provide simpler proofs for some of the known reductions.
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149420 |
| _version_ | 1811087698742476800 |
|---|---|
| author | Herrmann, Paul Peter |
| author_facet | Herrmann, Paul Peter |
| author_sort | Herrmann, Paul Peter |
| collection | MIT |
| description | A large class of combinatorial problems have been shown by Cook and Karp to be computationally equivalent to within a polynomial. We exhibit some new problems in this class, and provide simpler proofs for some of the known reductions. |
| first_indexed | 2024-09-23T13:50:36Z |
| id | mit-1721.1/149420 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:50:36Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1494202023-03-30T03:35:42Z On Reducibility Among Combinatorial Problems Herrmann, Paul Peter A large class of combinatorial problems have been shown by Cook and Karp to be computationally equivalent to within a polynomial. We exhibit some new problems in this class, and provide simpler proofs for some of the known reductions. 2023-03-29T14:57:25Z 2023-03-29T14:57:25Z 1973-12 https://hdl.handle.net/1721.1/149420 08229072 MIT-LCS-TR-113 MAC-TR-113 application/pdf |
| spellingShingle | Herrmann, Paul Peter On Reducibility Among Combinatorial Problems |
| title | On Reducibility Among Combinatorial Problems |
| title_full | On Reducibility Among Combinatorial Problems |
| title_fullStr | On Reducibility Among Combinatorial Problems |
| title_full_unstemmed | On Reducibility Among Combinatorial Problems |
| title_short | On Reducibility Among Combinatorial Problems |
| title_sort | on reducibility among combinatorial problems |
| url | https://hdl.handle.net/1721.1/149420 |
| work_keys_str_mv | AT herrmannpaulpeter onreducibilityamongcombinatorialproblems |