Exact-counting task in OpenAI's ETH manuscript
The introductory task takes a formula F with n declared variables and m clauses, and asks for the exact integer #F. The paper encodes each clause with exactly k literal positions, including repeats. It fixes k while considering inputs with larger n. For any one input, the formula and declared variable list stay fixed while assignments vary.
Take F = (p OR q) AND (r), with declared variables p, q, r. For k = 2, encode it as (p OR q) AND (r OR r). Repeating r preserves which assignments work. Here n = 3 and m = 2. To satisfy F, r must be true; the allowed (p, q) pairs are (false, true), (true, false), and (true, true). Thus #F = 3, and 3 > 0 gives the decision answer YES.
The paper writes false as 0 and true as 1: equation (1.1) counts the assignments for which F evaluates to 1. This example explains the input and output, not the algorithm, theorem or running-time bounds.
0
1
Tags
Math