INTRACTABILITY IN LINEAR SWITCH-LEVEL SIMULATION

The linear switch-level model represents a MOS transistor as a voltage -controlled linear resistor and a storage node as a grounded, linear c apacitor. For logic simulation, the linear switch-level model offers a n attractive trade-off between resolution/accuracy and computational c omplexity over gate level and circuit-level models. However, analysis of MOS networks using the linear switch-level model becomes increasing ly difficult in the presence of unknown values, such as logic X, and h euristic methods are often employed. This paper shows the complexity o f computing maximum and minimum steady-state voltages of a general MOS network using the linear switch-level model in the presence of unknow n values to be NP-complete. These results partially justify the use of heuristic methods when unknown values are present.