5 ms·

Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum SETH has a sub quadratic lower bound and several other grap

Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum SETH has a sub quadratic lower bound and several other graph problems have cubic lower bounds. Many real systems are often saved because it is actually hard to write code that aren't primitive recursive functions. Cycles often are what destroy that, as considering WHILE and GOTO being the difference between primitive and general recursive functions helps show. If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help. A graph data type wouldn't have those heuristics.

eru 3y ago
> Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum Those are lower bounds on worst case instances. Not lower bounds on solving typical, practical instances. > If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help. > A graph data type wouldn't have those heuristics. Sounds like your heuristic for why heuristics help with many NP problems is less than helpful here. In practice, you can encode many graph problems as eg SAT or integer programming or SMT etc and get good performance. Even biggish instances of eg the traveling salesman problem are often solved well in practice. I'm not sure why you bring up primitive recursive functions? Primitive recursion is able to express all of NP (and much more), so it's not much of a constraint in this discussion? (I agree that you have to try hard in practice to go beyond primitive recursion but stay finite.)