Abstract
Highly regular data can be represented succinctly by various kinds of implicit data structures. Many problems in P are known to be hard if their input is given as circuit or Ordered Binary Decision Diagram (OBDD). Nevertheless, in practical areas like CAD and Model Checking, symbolic algorithms using functional operations on OBDD-represented data are well-established. Their theoretical analysis has mostly been restricted to the number of functional operations yet. We show that P-complete problems have no symbolic algorithms using a polylogarithmic number of functional operations, unless P=NC. Moreover, we complement PSPACE-hardness results for problems on OBDD-represented inputs by fixed-parameter intractability results, where the OBDD width serves as the fixed parameter.
Extended version available at http://ls2-www.cs.uni-dortmund.de/s̃awitzki/.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Balcázar, J.L., Lozano, A.: The Complexity of Graph Problems for Succinctly Represented Graphs. In: Nagl, M. (ed.) WG 1989. LNCS, vol. 411, pp. 277–285. Springer, Heidelberg (1990)
Bryant, R.E.: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers 35, 677–691 (1986)
Chandra, A.K., Stockmeyer, L., Vishkin, U.: Constant Depth Reducibility. SIAM Journal on Computing 13(2), 423–439 (1984)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.: Complexity of Problems on Graphs Represented as OBDDs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 216–226. Springer, Heidelberg (1998)
Galperin, H., Wigderson, A.: Succinct Representations of Graphs. Information and Control 56, 183–198 (1983)
Gentilini, R., Piazza, C., Policriti, A.: Computing Strongly Connected Components in a Linear Number of Symbolic Steps. In: SODA 2003, pp. 573–582. ACM Press, New York (2003)
Gentilini, R., Policriti, A.: Biconnectivity on Symbolically Represented Graphs: A Linear Solution. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 554–564. Springer, Heidelberg (2003)
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation. Oxford University Press, New York (1995)
Hachtel, G.D., Somenzi, F.: Logic Synthesis and Verification Algorithms. Kluwer Academic Publishers, Boston (1996)
Hachtel, G.D., Somenzi, F.: A Symbolic Algorithm for Maximum Flow in 0–1 Networks. Formal Methods in System Design 10, 207–219 (1997)
Jones, N.D., Lien, Y.E., Laaser, W.T.: New Problems Complete for Nondeterministic Log Space. Mathematical Systems Theory 10, 1–17 (1976)
Nunkesser, R., Woelfel, P.: Representation of Graphs by OBDDs. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 1132–1142. Springer, Heidelberg (2005)
Papadimitriou, C.H., Yannakakis, M.: A Note on Succinct Representations of Graphs. Information and Control 71, 181–185 (1986)
Sawitzki, D.: Experimental Studies of Symbolic Shortest-Path Algorithms. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol. 3059, pp. 482–497. Springer, Heidelberg (2004)
Sawitzki, D.: Implicit Flow Maximization by Iterative Squaring. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 301–313. Springer, Heidelberg (2004)
Sawitzki, D.: On Graphs with Characteristic Bounded-Width Functions. Technical Report, University of Dortmund (2004)
Sawitzki, D.: A Symbolic Approach to the All-Pairs Shortest-Paths Problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 154–167. Springer, Heidelberg (2004)
Sieling, D., Wegener, I.: NC-Algorithms for Operations on Binary Decision Diagrams. Parallel Processing Letters 3, 3–12 (1993)
Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM, Philadelphia (2000)
Woelfel, P.: Symbolic Topological Sorting with OBDDs. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 671–680. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sawitzki, D. (2006). The Complexity of Problems on Implicitly Represented Inputs. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds) SOFSEM 2006: Theory and Practice of Computer Science. SOFSEM 2006. Lecture Notes in Computer Science, vol 3831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11611257_45
Download citation
DOI: https://doi.org/10.1007/11611257_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31198-0
Online ISBN: 978-3-540-32217-7
eBook Packages: Computer ScienceComputer Science (R0)