Timeline for NP problem implications [closed]
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2013 at 2:02 | history | closed |
Emil Jeřábek Andreas Blass Chris Godsil Goldstern Brendan McKay |
off topic | |
| Jan 18, 2013 at 18:20 | comment | added | Stephan Müller | That could be math.stackexchange.com but there are many other as well | |
| Jan 18, 2013 at 18:06 | comment | added | luca | ok, thank you for your help, and excuse me if I posted the question in the wrong site, I don't know any other. Thank you again. | |
| Jan 18, 2013 at 18:00 | comment | added | Emil Jeřábek | Anyway, this is not a research-level question, and as such it is not appropriate for this site. | |
| Jan 18, 2013 at 17:56 | comment | added | Emil Jeřábek | But if you can find a 3-edge partition, you have no information on the existence of 3-paths partition. A reduction has to be if and only if, otherwise it is useless. Let me give another example: 1') 3-colourability of graphs is NP-complete. If a graph has no 3-colouring, it has no 2-colouring either, hence by your logic, 2') 2-colourability of graphs is NP-complete. But this is wrong (unless P = NP), as 2-colourability is decidable in polynomial time. | |
| Jan 18, 2013 at 17:33 | comment | added | luca | you're right, but if I know that I can't find any partition of 3 edge connected component then I'm sure that I can't find a partition with 3-paths (which are 3 edge connected component) So, 1)----->2) | |
| Jan 18, 2013 at 17:14 | comment | added | Emil Jeřábek | If you know that a graph cannot be partitioned into 3-paths, how does it help you to determine whether it can be partitioned into 3-edge components? | |
| Jan 18, 2013 at 17:01 | history | asked | luca | CC BY-SA 3.0 |