2 ms·
Because Graph Three Colouring[0][1] is NP-Complete[2][3] we can use it to solve any NP problem. Integer factoring is an NP problem[4] so we should be able to f
by ColinWright 11y ago
Because Graph Three Colouring[0][1] is NP-Complete[2][3] we can use it to solve any NP problem. Integer factoring is an NP problem[4] so we should be able to factor integers by using Graph Three Colouring.
This post shows one way of doing that, and explains the techniques used to show directly that Graph Three Colouring is NP-Complete.
[0] http://www.solipsys.co.uk/new/GraphThreeColouring.html?HN_20151223 http://www.solipsys.co.uk/new/GraphThreeColouring.html?HN_20...
[1] https://news.ycombinator.com/item?id=10758236 https://news.ycombinator.com/item?id=10758236
[2] https://en.wikipedia.org/wiki/NP-completeness https://en.wikipedia.org/wiki/NP-completeness
[3] https://www.youtube.com/watch?feature=player_embedded&v=YX40hbAHx3s https://www.youtube.com/watch?feature=player_embedded&v=YX40...
[4] https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity https://en.wikipedia.org/wiki/Integer_factorization#Difficul...