Let L1, ..., Ls be the zero-one values of the literals in one clause. Its satisfaction indicator is Phi = 1 - (1-L1)...(1-Ls), where adjacent parentheses are multiplied. If all literals are false, every factor is 1 and Phi = 0. If any literal is true, its factor is 0 and Phi = 1. For p OR NOT q, Phi(x,y) = 1 - (1-x)y. On assignments (x,y) = (0,0), (0,1), (1,0), (1,1), the outputs are 1, 0, 1, 1. This zero-one interpretation is guaranteed only for Boolean inputs.

A polynomial that indicates whether a clause is satisfied

Here a Boolean-indexed tensor is a function T that takes an ordered list of d bits and returns one number or ring element. The d input positions are called ports. For d=2, the entries T(0,0), T(0,1), T(1,0), T(1,1) form a two-by-two table. Boolean describes the indices, not the values: entries can be integers or truncated polynomials. For d=0, the tensor has one scalar entry. A tensor can be described by a procedure that computes a requested entry rather than by explicitly storing all 2^d entries.

A Boolean-indexed tensor is a local table or entry rule

Write false as 0 and true as 1. A truth assignment then becomes a list of bits, one for each declared variable. If p has bit x, the positive literal p has value x and NOT p has value 1 - x: when x = 0 the negation has value 1, and when x = 1 it has value 0. These are ordinary integer calculations, not arithmetic modulo 2. This encoding lets a numerical expression represent whether a literal is true.

AI Agents

A truth assignment chooses true or false for every distinct variable in a declared list. For the list p, q, the four assignments are (false, false), (false, true), (true, false), and (true, true). To add a new declared variable r, extend each assignment once with r = false and once with r = true. This gives two extensions for each old assignment, doubling the list from four to eight. A declared variable still gets a value even if it never appears in the formula (logical expression).

Truth assignments over a declared variable set

OpenAI. The Exponential Time Hypothesis is False. Manuscript dated October 17, 2026, revised October 25, 2026. This reference pins commit 42907c9e999cc00d6abe7a50bfc1023250edd1b9. The introduction defines the exact-counting task used by this learning path; citing it does not establish that its main theorem is correct.

https://github.com/openai/math/blob/42907c9e999cc00d6abe7a50bfc1023250edd1b9/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf

OpenAI: The Exponential Time Hypothesis is False (October 25, 2026 revision)

A satisfying assignment makes every clause of a CNF formula true. For a specified declared variable list, #F means the number of distinct assignments that satisfy F. It counts assignments, not true clauses. For F = (p OR q) AND (NOT p) over p, q, only p = false and q = true works, so #F = 1. If an unused variable r is also declared, either value of r works and #F = 2. Exact counting returns this integer, not an estimate.

Learn Before

Related

Learn After

Learn After

Related