4 ms·
> in 2D layout is NP-hard (complete) without efficient polynomial approximations; in 3D layout is low-order polynomial Any chance you could explain to a novice
by yjftsjthsd-h 5y ago
> in 2D layout is NP-hard (complete) without efficient polynomial approximations; in 3D layout is low-order polynomial
Any chance you could explain to a novice why 3D is easier? To my naive intuition, it would have seemed like the more room to maneuver is offset by having more stuff to route.
- thechao 5y agoTry laying out a square with all the vertices connected in a plane: it’s not possible. You must move one of the wires “up” a layer. Which wire? Great layout minimizes layer transitions while also bunching together related HW blocks. The NP-completeness proof is related to work Knuth’s student (Plass?) did on laying out images in TeX.
- blt 5y agoIntuitively, we feel that larger solution spaces should make a problem harder because there are more possible solutions to consider. And of course this is true if exhaustive search is the only algorithm. But CS is full of problems where the smaller space is NP-hard and the larger one isn't. Integer linear programming is a prominent example. To resolve the intuition, we can think of the larger space as an "unconstrained" problem where the solution space is somehow natural and nice for the problem. From this perspective, the smaller space looks like an added constraint. Adding constraints usually makes problems harder.
- dragontamer 5y ago> Adding constraints usually makes problems harder. Adding constraints can also make a problem easier. Which is why you've carefully worded your sentence in this manner :-) You clearly know about those edge cases, but I felt it necessary to elaborate on this point: Additional constraints can make a problem easier OR harder, depending on the problem and the search space. Its very non-intuitive.