A112535 Number of truth tables generated by 3CNF expressions of n variables.

2, 4, 16, 256, 43146, 120510132, 4977694100656

Offset: 0

Author

C. Bradford Barber (bradb(AT)shore.net), Dec 13 2005

Keywords

• nonn
• hard

Comments

For n=5, computing the number of 3CNF truth tables took 2^32 bytes and 2^38 iterations. Computing the same number for n=6 may require 2^64 bits and 2^71 iterations.

I calculated a(6) using a different method; a(7) looks a lot harder. - Don Knuth, Dec 10 2012

References

• Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 148 and 220, Problem 191.

Links

• C. B. Barber, ttcnf 2005.1 (April 2005).
• C. B. Barber, www.qhull.org/ttcnf.

Crossrefs

Cf. A034472, A109457 (corresponding sequences for 1CNF and 2CNF), A112650, A000157, A000371, A000613, A000618, A003181.

Extensions

a(6) from Don Knuth, Dec 10 2012