Post Reply 
Challenge: sum of squares. Let's break 299
01-20-2018, 10:13 PM
Post: #18
RE: Challenge: sum of squares. Let's break 299
(01-20-2018 05:43 PM)Thomas Okken Wrote:  What's NP-complete is the problem of finding Hamilton paths in graphs in general. For certain specific classes of graphs, that doesn't necessarily apply, like graphs where no node connects to more than two edges. The lady in the video, who wrote the program that checked all cases up to 299, must have found something to exploit, because with the apparently roughly exponential way the CPU time in my algorithm increases, it wouldn't get to 299 in a million years, even if I parallellized the heck out of it and ran it on the GPU clusters at work. (I should let it run a bit longer than I have so far to see how the CPU usage evolves, though.)

I think there was mention of trying to link the new node directly into the previous graph. Starting the search from there feels like it would be a win. It kind of makes sense that much of the graph will often be unchanged with the addition of a new node. Still exponential time problems always become infeasible.

Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-20-2018 10:13 PM

User(s) browsing this thread: 1 Guest(s)