Anybody know if *optimal* (not real/practical) FPGA/ASIC routing is NP-hard or harder than that?
-
-
Replying to @azonenberg
Gut feeling: you cannot tell if a given placement/routing is best possible w/o examining an exponential number of alternatives
2 replies 0 retweets 1 like -
Replying to @azonenberg
You can constrain "cost < K" and decrease K when SAT, increase when UNSAT. Takes a logarithmic number of runs. Looks NP to me.
1 reply 0 retweets 2 likes
Replying to @oe1cxw @azonenberg
That's essentially how all NP optimization problems relate to the underlying NP decision problem.
5:45 AM - 24 Nov 2016
0 replies
0 retweets
0 likes
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.