scientific article; zbMATH DE number 4037759

From MaRDI portal
Publication:3777937





[For the entire collection see Zbl 0624.00026.] Under the assumption that encryption functions exist, we show that all languages in NP possess zero-knowledge proofs. That is, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula. In particular, without yieldinChannel routing is an important subcase of the layout design problem for VLSI circuits. In the paper an exact model for channel routing is developed and some special variants of the problem are considered. For river routing and channel routing without vertical constraints results concerning complexity and necessary track number are given. For the case of channel routing with vertical constraints upper and lower bounds for the track number and an approximate routing algorithm are derived.




Cited in
(70)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777937)