Complexity Classifications for Different Equivalence and Audit Problems for Boolean Circuits

Article, Preprint English OPEN
Böhler, Elmar ; Creignou, Nadia ; Galota, Matthias ; Reith, Steffen ; Schnoor, Henning ; Vollmer, Heribert (2016)
  • Publisher: Tech. Univ. Braunschweig
  • Related identifiers: doi: 10.2168/LMCS-8(3:31)2012, doi: 10.15488/1988
  • Subject: satisfiability problems | Informatik | Computer Science - Computational Complexity | hierarchy | boolean circuits | complexity classification | F.2.2 | isomorphism
    • ddc: ddc:004
    arxiv: Computer Science::Hardware Architecture | Computer Science::Emerging Technologies
    acm: Hardware_LOGICDESIGN

We study Boolean circuits as a representation of Boolean functions and conskier different equivalence, audit, and enumeration problems. For a number of restricted sets of gate types (bases) we obtain efficient algorithms, while for all other gate types we show these problems are at least NP-hard.
  • References (31)
    31 references, page 1 of 4

    [AT00] M. Agrawal and T. Thierauf. The formula isomorphism problem. SIAM Journal on Computing, 30(3):990-1009, 2000.

    [BCRV03] E. B¨ohler, N. Creignou, S. Reith, and H. Vollmer. Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. ACM SIGACT-Newsletter, 35(4):38-52, 2003.

    [BG82] A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and Control, 82:80- 88, 1982.

    [CGH+88] J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The Boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232 - 1252, December 1988.

    [CGH+89] J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The Boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95 - 111, February 1989.

    [CH97] N. Creignou and J.-J. H´ebrard. On generating all solutions of generalized satisfiability problems. Informatique Th´eorique et Applications/Theoretical Informatics and Applications, 31(6):499-511, 1997.

    [CKS00] N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. Monographs on Discrete Applied Mathematics. SIAM, 2000.

    N. Creignou and H. Vollmer. Boolean constraint satisfaction problems: When does Post's lattice help? In Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer, editors, Complexity of Constraints, volume 5250 of Lecture Notes in Computer Science, pages 3-37. Springer, 2008.

    Inf. Process. Lett., 27(3):119-123, 1988.

    D.S. Johnson, M. Yannakakis, and C.H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27:119-123, 1988.

  • Metrics
    No metrics available