The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments | Algorithmica Skip to main content
Springer Nature Link
Log in

The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study the exponential time complexity of approximate counting satisfying assignments of CNFs. We reduce the problem to deciding satisfiability of a CNF. Our reduction preserves the number of variables of the input formula and thus also preserves the exponential complexity of approximate counting. Our algorithm is also similar to an algorithm which works particularly well in practice and for which no approximation guarantee is known.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. The notation \(O^*(\cdot )\) suppresses a polynomial factor.

  2. Pairwise independence means that \(\Pr _{h\sim \mathcal {H}_\text {ind}}(h(x_1)=y_1,h(x_2)=y_2) = 2^{-2m}\) for any \(x_1,x_2\in \{0,1\}^n\), \(x_1\not =x_2\), and \(y_1,y_2\in \{0,1\}^m\). An \(m\times n\) Bernoulli matrix with probability \(\frac{1}{2}\) induces a pairwise independent family.

  3. See Sect. 2.

References

  1. Beckner, W.: Inequalities in Fourier analysis. Ann. Math. 102, 159–182 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bonami, A.: Étude des coefficients des Fourier de fonctions de \(L\mathit{^p(G})\). Annales de l’Institut Fourier 20(2), 335–402 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  3. Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of Unique \(k\)-SAT: an isolation lemma for \(k\)-CNFs. J. Comput. Syst. Sci. 74(3), 386–393 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, pp. 252–260 (2006)

  5. Calabro, C., Impagliazzo, R., Paturi, R.: On the exact complexity of evaluating quantified k-CNF. Algorithmica 65(4), 817–827 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chor, B., Goldreich, O.: On the power of two-point based sampling. J. Complex. 5(1), 96–106 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cooper, C.: On the rank of random matrices. Random Struct. Algorithms 16(2), 209–232 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. de Wolf, R.: A brief introduction to Fourier analysis on the Boolean cube. Theory Comput. Library Grad. Surv. 1, 1–20 (2008)

    Google Scholar 

  9. Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B.: Taming the curse of dimensionality: discrete integration by hashing and optimization. In: Proceedings of the 30th International Conference on Machine Learning, pp. 334–342 (2013)

  10. Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B.: Low-density parity constraints for hashing-based discrete integration. In: Proceedings of the 31th International Conference on Machine Learning, pp. 271–279 (2014)

  11. Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., de Wolf, R.: Exponential separations for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput. 38(5), 1695–1708 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gomes, C.P., Sabharwal, A., Selman, B.: Model counting: a new strategy for obtaining good bounds. In: Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference (2006)

  13. Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 12–24 (1989)

  14. Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC0. In: Proceedings of the 23th ACM-SIAM Symposium on Discrete Algorithms, pp. 961–972 (2012)

  15. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  16. Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169–188 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  17. Jukna, S.: Extremal Combinatorics. Springer, Berlin (2001)

    Book  MATH  Google Scholar 

  18. Kahn, J., Kalai, G., Linial, N.: The influence of variables on Boolean functions. In: Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 68–80 (1988)

  19. O’Donnell, R.: Some topics in analysis of boolean functions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 569–578 (2008)

  20. Pătraşcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pp. 1065–1075 (2010)

  21. Stockmeyer, L.J.: On approximation algorithms for #P. SIAM J. Comput. 14(4), 849–861 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  22. Thurley, M.: An approximation algorithm for #k-SAT. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, pp. 78–87 (2012)

  23. Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(1), 85–93 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  24. Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2), 357–365 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We thank the anonymous referees for their useful comments which helped to improve the readability and the discussion of the main results and lemmas.

Author information

Authors and Affiliations

  1. Software Competence Center Hagenberg, Hagenberg im Mühlkreis, Austria

    Patrick Traxler

Authors
  1. Patrick Traxler
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Patrick Traxler.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Traxler, P. The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments. Algorithmica 75, 339–362 (2016). https://doi.org/10.1007/s00453-016-0134-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0134-y

Keywords