= 27d567bc2d48d9f40e9ccc20ea370b15)
Plasmon comments on The Unique Games Conjecture and FAI: A Troubling Obstacle - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (25)
Real physics is local. The graphs, to the extent that there are any, are embedded in metric spaces, have small upper bounds on the number of edges per vertex, are planar, .... generally there is plenty of exploitable structure beyond the pure graph-theoretical problem. This is why I do not think hardness results on abstract graph-theoretical problems will be a great obstacle for practical problems.
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.
Where are you getting this from?
Every single physical theory that is currently considered fundamental is local, from general relativity to quantum mechanics.
I dislike the wikipedia article on the subject, it gives far to much credence to the fringe notion that maybe there is a way to exploit entanglement to get faster-than-light information transfer.
The quantum nonlocality article is much better, it correctly points out that
Does quantum nonlocality count as not being real physics?
I was unclear, of course it is real physics. By "real" I mean simply something that occurs in reality, which quantum nonlocality certainly does.
Quantum nonlocality - despite being named "nonlocality"- is actually local in a very important sense, just like the rest of physics : information never moves faster than c.
It follows from special relativity.