Timeline for Complexity of ANOTHER HAMILTONIAN CIRCUIT problem
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 1, 2017 at 18:56 | vote | accept | user1868607 | ||
| Sep 1, 2017 at 18:39 | history | edited | user1868607 | CC BY-SA 3.0 |
added 118 characters in body
|
| Sep 1, 2017 at 13:37 | comment | added | user1868607 | @j_random_hacker I updated with what seems to be the correct reduction but still have doubts | |
| Sep 1, 2017 at 13:36 | history | edited | user1868607 | CC BY-SA 3.0 |
added 786 characters in body
|
| Aug 31, 2017 at 23:27 | history | edited | user1868607 | CC BY-SA 3.0 |
added 112 characters in body
|
| Aug 31, 2017 at 22:36 | comment | added | j_random_hacker | I take back my earlier claim that there was a trivial reduction! I don't see any obvious way. | |
| Aug 31, 2017 at 20:46 | history | edited | Raphael |
edited tags
|
|
| Aug 31, 2017 at 19:53 | answer | added | Yuval Filmus | timeline score: 4 | |
| Aug 31, 2017 at 18:40 | comment | added | j_random_hacker | You need to reduce the Hamiltonian Circuit problem (or some other NP-hard problem) to this problem: That is, if you had a magic device for solving ANOTHER HAMILTONIAN CIRCUIT quickly, could you solve other hard problems with it too? | |
| Aug 31, 2017 at 18:21 | history | asked | user1868607 | CC BY-SA 3.0 |