The equivalence of theorem proving and the interconnection problem

ABSTRACT

A simple method of converting statements in mathematical logic to equivalent interconnection problems is demonstrated. This shows that if there exists a practical method for solving interconnection problems, then there exists a practical proof procedure for statements in mathematical logic. (In the terminology of Cook [1] and Karp [4], the interconnection problem is NP-complete.) Since such a procedure has been sought for without success for almost 100 years, we should not expect the interconnection problem to be any easier. This holds equally true for finding a method which will route a given percentage of wires.

REFERENCES

• 1: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 2: Frege, G. <u>Begriffsschrift, eine der Arithmetischen Nachgebildete Formelsprache des Reinen Denkens</u>, Halle, 1879.
• 3: M. R. Garey , D. S. Johnson , L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803884]
• 4: Karp, R. M. "Reducibility Among Combinatorial Problems." <u>Complexity of Computer Computations</u>, Miller and Thatcher, eds., Plenum Press, 1972, pp. 85--104.