[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We study the complexity of equivalence and isomorphism on primitive positive formulas with respect to a given structure. We study these problems for various fixed structures; we present generic hardness and complexity class containment results, and give classification theorems for the case of two-element (boolean) structures.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Agrawal, M., Thierauf, T.: The formula isomorphism problem. SIAM J. Comput. 30(3), 990–1009 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  2. Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer’s theorem. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS (2005)

    Google Scholar 

  3. Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer’s theorem. J. Comput. Syst. Sci. 75(4), 245–254 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  4. Atserias, A.: Conjunctive query evaluation by search-tree revisited. Theor. Comput. Sci. 371(3), 155–168 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  5. Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254–276 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  6. Berman, J., Idziak, P., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Am. Math. Soc. (2009). doi:10.1090/S0002-9947-09-04874-0

    Google Scholar 

  7. Bodnarchuk, V., Kaluzhnin, L., Kotov, V., Romov, B.: Galois theory for post algebras. I, II. Cybernetics 5:243–252, 531–539 (1969)

    Article  Google Scholar 

  8. Böhler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence and isomorphism for boolean constraint satisfaction. In: Proceedings of the 16th International Workshop on Computer Science Logic, CSL (2002)

    Google Scholar 

  9. Böhler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: The complexity of boolean constraint isomorphism. In: Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS (2004)

    Google Scholar 

  10. Boppana, R., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  11. Bulatov, A., Jeavons, P.: Algebraic structures in combinatorial problems. Technical Report MATH-AL-4-2001, Technische Universitat Dresden (2001)

  12. Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720–742 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  13. Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2001)

    Book  Google Scholar 

  14. Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27, 95–100 (1968)

    MATH  MathSciNet  Google Scholar 

  15. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 690–728 (1991)

    Article  MathSciNet  Google Scholar 

  16. Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC (1986)

    Google Scholar 

  17. Hobby, D., McKenzie, R.: The Structure of Finite Algebras. Contemporary Mathematics, vol. 76. Am. Math. Soc., Providence (1988)

    Google Scholar 

  18. Idziak, P., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. In: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS (2007)

    Google Scholar 

  19. Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency, and closure. Artif. Intell. 101(1–2), 251–265 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  20. Kobler, J., Schöning, U., Toran, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, Basel (1993)

    Google Scholar 

  21. Kolaitis, P., Vardi, M.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 302–332 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  22. Ladner, R.: On the structure of polynomial time reducibility. J. ACM 22(1), 155–171 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  23. Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci. (2008). doi:10.1016/j.tcs.2008.12.048

    Google Scholar 

  24. Nordh, G.: The complexity of equivalence and isomorphism of systems of equations over finite groups. Theor. Comput. Sci. 345(2–3), 406–424 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  25. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1995)

    Google Scholar 

  26. Papadimitriou, C., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407–427 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  27. Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC (1978)

    Google Scholar 

  28. Schoning, U.: Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37(3), 312–323 (1988)

    Article  MathSciNet  Google Scholar 

  29. Szendrei, A.: Clones in Universal Algebra. Seminaires de Mathematiques Superieures, vol. 99. University of Montreal, Montreal (1986)

    MATH  Google Scholar 

  30. Szendrei, A.: A Survey on Strictly Simple Algebras and Minimal Varieties. Research and Exposition in Mathematics, vol. 19, pp. 209–239. Heldermann, Berlin (1992)

    Google Scholar 

  31. Toran, J.: On the hardness of graph isomorphism. SIAM J. Comput. 33(5), 1093–1108 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  32. Valeriote, M.: A subalgebra intersection property for congruence distributive varieties. Can. J. Math. (2009). doi:10.4153/CJM-2009-023-2

    MathSciNet  Google Scholar 

  33. Vardi, M.: The complexity of relational query languages. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Vanderbilt University, Nashville, USA

    Simone Bova

  2. Departament de Tecnologies de la Informació i les Comunicacions, Universitat Pompeu Fabra, Barcelona, Spain

    Hubie Chen

  3. Department of Mathematics & Statistics, McMaster University, Hamilton, Canada

    Matthew Valeriote

Authors
  1. Simone Bova
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hubie Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matthew Valeriote
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hubie Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bova, S., Chen, H. & Valeriote, M. On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas. Theory Comput Syst 50, 329–353 (2012). https://doi.org/10.1007/s00224-010-9302-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-010-9302-7

Keywords

Search

Navigation