Timeline for CLIQUE $\leq_p$ SAT
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2019 at 14:17 | vote | accept | gxor | ||
| Aug 14, 2019 at 8:31 | answer | added | Yuval Filmus | timeline score: 5 | |
| Aug 13, 2019 at 15:21 | comment | added | gxor | Yes I know that for normal people do it the other way around. I was just trying to challenge me as in a video i was watching the it said that the way CLIQUE <= SAT is easy to show. Constructing a NTM is easy indeed! I was just trying to exercise my reduction skills! | |
| Aug 13, 2019 at 14:24 | comment | added | dkaeae | Also note that, although not very enlightening, you can achieve what you want by constructing an NTM for clique and then using the construction from the Cook-Levin theorem on said NTM. This might be the fastest (or laziest) way of obtaining the reduction. | |
| Aug 13, 2019 at 14:21 | comment | added | dkaeae | Is there a particular reason you are trying to reduce clique to SAT and not the other way around? Assuming your goal is establishing NP-completeness of clique, usually one proves it by showing clique is in NP (a rather trivial matter) followed by establishing a reduction from 3SAT to clique (using appropriate graph gadgets). | |
| Aug 13, 2019 at 14:09 | history | asked | gxor | CC BY-SA 4.0 |