In mathematics, satisfying constraints is called an optimization problem.
We won't get far if we start twisting basic mathematical terms.
Functions may have minimums and maximums. Since the same methods can deal with minimums and maximums, they often called optimums. An optimum can be either maximum or minimum.
The task of finding minimums is called minimization. The task of finding maximums is called maximization. The task of finding optimums is called optimization.
The optimization may be complicated with constraints - which finds the optimum in the sub-space of the inputs defined by the constraints.
Often optimization cannot be performed computationally within reasonable time (what you call NP-hard). In this situation, finding a point which is close enough to the optimum gives you approximate solution.
Finding an arbitrary point in the constrained sub-space is not optimisation. Contrary to the optimization, this task does not have any approximate solution. They point either lies within the constraints, or it doesn't. It cannot be more within constraints, or less within constraints. It is either in or not. Makes sense so far?
This is what happens in FPGA. There are constraints, predominantly timing constraints. If these constraints are met the design will work across specified conditions. If not, the design may fail. Very simple.
In the case of FPGA synthesis, one would most likely want to apply weights to the error terms so that the bounds on the high speed portions are tighter than on the low speed portions. So different weights would be applied to different errors in the minimization expression.
FPGA uses RTL logic model (stands for Register Transfer Logic), which includes sequential elements (often called registers or flip-flops) and combinatorial logic between them (various gates, LUTs, muxes, interconnect etc.).
When a clock hits a flip-flop, the input of the flip-flop gets registered, transferred to the output and starts to propagate through the combinatorial logic to the next sequential element where it is supposed to be registered on the next(for simplicity) clock edge.
The delay through combinatorial logic is generally unpredictable - it varies from FET to FET, depends on the process, voltage, temperature. But the vendor performs characterization work - they measure the delays for thousands of FPGAs and across all the various conditions and they come up with two numbers - minimum delay and maximum delay. The vendor does this for each and every elements within FPGA.
Once these numbers are known, you can sum them up across the combinatorial path and use the numbers to determine whether the design is acceptable or not. This is done with two comparisons.
1. The combined minimum delay must be big enough to make sure that by the time the signal propagates to the next sequential element, this next sequential element has already done working with its previous input. This is defined by the "Hold" characteristic - the time starting from the clock edge and ending at the point in time where the register doesn't need the input any more.
2. The combined maximum delay must be small enough to make sure that the signal gets to the next sequential element before the sequential element starts registering the signal. This is defined by the "Setup" characteristic - the time starting from the point when the register must have valid input to the clock edge.
Thus the sequence of events should be such:
clock edge - hold expires - new data arrives - setup point - next clock edge
Note that the uncertainty of the delays doesn't propagate to the next clock cycle and doesn't accumulate. Each clock cycle starts anew, error free (not counting clock jitter). This feature lets the RTL system work for very long periods of time without errors.
However, for the RTL system to work, the events must happen in exact order (clock-hold-data-setup-clock) regardless of the conditions - voltage, temperature etc. If data arrives before hold or after setup even for one single flip-flop in your FPGA, the whole design may be doomed. Worse yet, the flip flop clocked when the input is unstable may become metastable.
Therefore, the design must meet the timing constraints. The solution cannot be approached or done approximately. The constraints must be met. And vice versa, once the constraints are met, there's no reason to tweak things any further - the design is guaranteed to work anyway. Makes sense?