Real physics is local, but many practical problems require understanding how the local aspects interact. Consider for example the traveling salesman: this is a purely local problem in statement, but many versions or variants of it occur in practical contexts where actually solving hard instances matters. For example, the bottleneck version shows up in circuit board design. Similarly, graph bandwith is “local” in nature but shows up in chip design, and tough instances do show up in practice. Similarly the pathwidth probem has practical applications in compiler design,general circuit design, and CPU design.
This also fails to appreciate the central interesting thing about UGC: hardness of UGC translates into hardness of approximating many problems which are not phrased in a graph way. Many different NP-complete problems have practical applications, not just for an AI trying to go Foom but also industrial applications now. Consider for example the cutting stock problem which has variants relevant to many different industries and where slightly better solutions really do lead to real savings.
It is also worth noting that this shouldn’t be surprising: most NP-complete problems are of the form where one can phrase the problem so that one has some sort of local information and one is interested in a solution that satisfies all the necessary local restrictions as well as some very weak global condition.
Real physics is local, but many practical problems require understanding how the local aspects interact. Consider for example the traveling salesman: this is a purely local problem in statement, but many versions or variants of it occur in practical contexts where actually solving hard instances matters. For example, the bottleneck version shows up in circuit board design. Similarly, graph bandwith is “local” in nature but shows up in chip design, and tough instances do show up in practice. Similarly the pathwidth probem has practical applications in compiler design,general circuit design, and CPU design.
This also fails to appreciate the central interesting thing about UGC: hardness of UGC translates into hardness of approximating many problems which are not phrased in a graph way. Many different NP-complete problems have practical applications, not just for an AI trying to go Foom but also industrial applications now. Consider for example the cutting stock problem which has variants relevant to many different industries and where slightly better solutions really do lead to real savings.
It is also worth noting that this shouldn’t be surprising: most NP-complete problems are of the form where one can phrase the problem so that one has some sort of local information and one is interested in a solution that satisfies all the necessary local restrictions as well as some very weak global condition.