News for hackers. Stuff that matters.
Re:Computing Performance on the Horizon by yjftsjthsd-h on Monday July 05, 2021 @04:41PM (#27741633)
> 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.

Re:Computing Performance on the Horizon by blt on Monday July 05, 2021 @08:00PM (#27742971)
Intuitively, 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.

Re:Computing Performance on the Horizon by dragontamer on Monday July 05, 2021 @08:47PM (#27743238)
> 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.

Re:Computing Performance on the Horizon by thechao on Monday July 05, 2021 @05:15PM (#27741878)
Try 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.