×

The complexity of minimizing and learning OBDDs and FBDDs. (English) Zbl 1002.68032

Summary: Ordered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs) are data structures for Boolean functions. They can efficiently be manipulated if only OBDDs respecting a fixed variable ordering or FBDDs respecting a fixed graph ordering are considered. In this paper, it is shown that the existence of polynomial time approximation schemes for optimizing variable orderings or graph orderings implies NP=P, and so such algorithms are quite unlikely to exist. Similar hardness results are shown for the related problems of computing minimal size OBDDs and FBDDs that are consistent with a given set of examples. The latter result implies that size bounded OBDDs and FBDDs are not PAC-learnable unless NP=RP.

MSC:

68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, in: Proceedings of 33rd Symposium on Foundations of Computer Science, 1992, pp. 14-23.; S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, in: Proceedings of 33rd Symposium on Foundations of Computer Science, 1992, pp. 14-23. · Zbl 0977.68539
[2] Bern, J.; Meinel, C.; Slobodová, A., Some heuristics for generating tree-like FBDD types, IEEE Trans. Comput. Aided Des. Integrated Circuits Systems, 15, 127-130 (1996)
[3] Bollig, B.; Wegener, I., Improving the variable ordering of OBDDs is NP-complete, IEEE Trans. Comput., 45, 993-1002 (1996) · Zbl 1048.68571
[4] Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., 35, 677-691 (1986) · Zbl 0593.94022
[5] S. Fortune, J. Hopcroft, E.M. Schmidt, The complexity of equivalence and containment for free single variable program schemes, in: Proceedings of Fifth International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 62, Springer, Berlin, 1978, pp. 227-240.; S. Fortune, J. Hopcroft, E.M. Schmidt, The complexity of equivalence and containment for free single variable program schemes, in: Proceedings of Fifth International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 62, Springer, Berlin, 1978, pp. 227-240. · Zbl 0382.68021
[6] Friedman, S. J.; Supowit, K. J., Finding the optimal variable ordering for binary decision diagrams, IEEE Trans. Comput., 39, 710-713 (1990) · Zbl 1395.68100
[7] M. Fujita, H. Fujisawa, N. Kawato, Evaluation and improvements of Boolean comparison method based on binary decision diagrams, in: International Conference on Computer-Aided Design, 1988, pp. 2-5.; M. Fujita, H. Fujisawa, N. Kawato, Evaluation and improvements of Boolean comparison method based on binary decision diagrams, in: International Conference on Computer-Aided Design, 1988, pp. 2-5.
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039
[9] Gergov, J.; Meinel, C., Efficient Boolean manipulation with OBDD’s can be extended to FBDD’s, IEEE Trans. Comput., 43, 1197-1209 (1994) · Zbl 1063.68573
[10] W. Günther, R. Drechsler, Minimization of free BDDs, in: Proceedings of Asia and South Pacific Design Automation Conference, 1999, pp. 323-326.; W. Günther, R. Drechsler, Minimization of free BDDs, in: Proceedings of Asia and South Pacific Design Automation Conference, 1999, pp. 323-326.
[11] S. Malik, A.R. Wang, R.K. Brayton, A. Sangiovanni-Vincentelli, Logic verification using binary decision diagrams in a logic synthesis environment, in: International Conference on Computer-Aided Design, 1988, pp. 6-9.; S. Malik, A.R. Wang, R.K. Brayton, A. Sangiovanni-Vincentelli, Logic verification using binary decision diagrams in a logic synthesis environment, in: International Conference on Computer-Aided Design, 1988, pp. 6-9.
[12] C. Meinel, A. Slobodová, On the complexity of constructing optimal ordered binary decision diagrams, in: Proceedings of 19th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 841, Springer, Berlin, 1994, pp. 515-524.; C. Meinel, A. Slobodová, On the complexity of constructing optimal ordered binary decision diagrams, in: Proceedings of 19th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 841, Springer, Berlin, 1994, pp. 515-524.
[13] Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation, and complexity classes, J. Comput. System Sci., 43, 425-440 (1991) · Zbl 0765.68036
[14] Pitt, L.; Valiant, L. G., Computational limitations on learning from examples, J. Assoc. Comput. Mac., 35, 965-984 (1988) · Zbl 0662.68086
[15] R. Rudell, Dynamic variable ordering for ordered binary decision diagrams, in: Proceedings of International Conference on Computer-Aided Design, 1993, pp. 42-47.; R. Rudell, Dynamic variable ordering for ordered binary decision diagrams, in: Proceedings of International Conference on Computer-Aided Design, 1993, pp. 42-47.
[16] D. Sieling, Algorithmen und untere Schranken für verallgemeinerte OBDDs, Ph.D. Thesis, Universität Dortmund. Shaker, Aachen, 1995 (in German).; D. Sieling, Algorithmen und untere Schranken für verallgemeinerte OBDDs, Ph.D. Thesis, Universität Dortmund. Shaker, Aachen, 1995 (in German).
[17] D. Sieling, On the existence of polynomial time approximation schemes for OBDD-minimization (extended abstract), in: Proceedings of 15th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1373, Springer, Berlin, 1998, pp. 205-215.; D. Sieling, On the existence of polynomial time approximation schemes for OBDD-minimization (extended abstract), in: Proceedings of 15th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1373, Springer, Berlin, 1998, pp. 205-215.
[18] D. Sieling, The nonapproximability of OBDD minimization, Information and Computation 172 (2002) 103-138.; D. Sieling, The nonapproximability of OBDD minimization, Information and Computation 172 (2002) 103-138. · Zbl 1009.68057
[19] D. Sieling, The complexity of minimizing FBDDs (extended abstract), in: Proceedings of 24th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1672, Springer, Berlin, 1999, pp. 251-261.; D. Sieling, The complexity of minimizing FBDDs (extended abstract), in: Proceedings of 24th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1672, Springer, Berlin, 1999, pp. 251-261. · Zbl 0955.68090
[20] Sieling, D.; Wegener, I., Graph driven BDDs—a new data structure for Boolean functions, Theoret. Comput. Sci., 141, 283-310 (1995) · Zbl 0873.68036
[21] J. Simon, M. Szegedy, A new lower bound theorem for read-only-once branching programs and its applications, in: Jin-Yi Cai (Ed.), Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, American Mathematical Society, Providence, RI, 1993, pp. 183-193.; J. Simon, M. Szegedy, A new lower bound theorem for read-only-once branching programs and its applications, in: Jin-Yi Cai (Ed.), Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, American Mathematical Society, Providence, RI, 1993, pp. 183-193. · Zbl 0801.68077
[22] Takenaga, Y.; Yajima, S., Hardness of identifying the minimum ordered binary decision diagram, Discrete Appl. Math., 107, 191-201 (2000) · Zbl 0965.68076
[23] S. Tani, K. Hamaguchi, S. Yajima, The complexity of the optimal variable ordering problems of shared binary decision diagrams, in: Proceedings of Fourth International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 762, Springer, Berlin, 1993, pp. 389-398.; S. Tani, K. Hamaguchi, S. Yajima, The complexity of the optimal variable ordering problems of shared binary decision diagrams, in: Proceedings of Fourth International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 762, Springer, Berlin, 1993, pp. 389-398. · Zbl 0925.68198
[24] Valiant, L. G., A theory of the learnable, Comm. ACM, 27, 1134-1142 (1984) · Zbl 0587.68077
[25] Wegener, I., On the complexity of branching programs and decision trees for clique functions, J. Assoc. Comput. Mac., 35, 461-461 (1988) · Zbl 0652.68063
[26] S. Žák, An exponential lower bound for one-time-only branching programs, in: Proceedings of 11th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 176, Springer, Berlin, 1984, pp. 562-566.; S. Žák, An exponential lower bound for one-time-only branching programs, in: Proceedings of 11th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 176, Springer, Berlin, 1984, pp. 562-566.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.