Timeline for Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 5, 2017 at 17:36 | comment | added | Sasho Nikolov | @devinbost I think (it's been a long long time) I was trying to get Ankush to specify what his actual constraints on the reduction are. Your answer seems to be that you want small blow up in the formula size. That's reasonable. I am not sure if it was what Ankush was looking for. | |
| Sep 5, 2017 at 8:01 | comment | added | devinbost | @SashoNikolov the issue with going from hamcycle -> sat -> 3-sat -> vertex cover is the number of variables generated by the sat that makes it very obnoxious to deal with. I'd much rather deal with the clique problem itself than the sat for that reason, but that's just me. | |
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Sep 19, 2012 at 4:42 | comment | added | Sasho Nikolov | but what is not constructive about Cook-Levin? it gives you a concrete construction: take you favorite verifier for hamcycle, encode it as a TM, build a SAT formula :) you want "simple" for some measure of simple? | |
| Aug 20, 2012 at 10:28 | comment | added | Ankush | @SashoNikolov nothing is wrong with it. If hamcycle to sat is a constructive proof that's fine. I'm looking for reductions which don't invoke Cook-Levin theorem. | |
| Aug 20, 2012 at 8:19 | comment | added | Sasho Nikolov | what's wrong with hamcycle->sat->3-sat->vertex cover? | |
| Aug 19, 2012 at 1:05 | answer | added | Luke Mathieson | timeline score: 2 | |
| Aug 18, 2012 at 18:32 | comment | added | user742 | I'd offer you to read Garey & Johnson book, they provide iff proof for some of problems, proof techniques are not easy and you can't expect to solve them yourself in few days. | |
| Aug 18, 2012 at 18:21 | comment | added | user742 | @Raphael, all of the mentioned problem by OP are strongly NP-C, so your comment makes no sense here. | |
| Aug 18, 2012 at 11:56 | history | tweeted | twitter.com/#!/StackCompSci/status/236793761210966017 | ||
| Aug 18, 2012 at 6:16 | comment | added | Raphael | Note that not all NPC problems are equally hard, see e.g. weakly vs strongly NP-completeness. Therefore, not all reductions are equally simple; those from strong to weak problems have to be complex enough to prevent e.g. efficient approximations to carry over (unless P=NP). | |
| Aug 17, 2012 at 22:28 | history | edited | Ankush | CC BY-SA 3.0 |
added 315 characters in body
|
| Aug 17, 2012 at 15:13 | comment | added | Ankush | @Chris As of now nothing. I mean till yesterday I was under impression that above isn't possible. Let me start with TSP to HAM-CYCLE :) | |
| Aug 17, 2012 at 14:40 | comment | added | Christopher | What have you tried? All stated problems are $\mathsf{NP}$-Complete. Thus every problem in $\mathsf{NP}$ can be reduced to your problems (by definition of $\mathsf{NPC}$). Hint: Start reducing TSP to HAM-CYCLE. | |
| Aug 17, 2012 at 14:34 | comment | added | Ankush | Well I found most reductions interesting because they are construction proofs. It's hard to think out-of-the-box constructions. So I wanted to see if reverse construction is possible. | |
| Aug 17, 2012 at 14:28 | comment | added | Christopher | Why are you interested in such reduction? Note: The last reduction 3CNF-SAT to SAT is trivial (Every 3CNF-SAT formula is a SAT formula). | |
| Aug 17, 2012 at 14:19 | history | asked | Ankush | CC BY-SA 3.0 |