.
polynomial time. So we have 𝑁𝑃 = 𝑃𝐶𝑃(𝑙𝑜𝑔(𝑛), 𝑝𝑜𝑦(𝑛)). But the big surprise is that once we allow logarithmically many coin tosses, we can in return reduce the number of queries 𝑞(𝑛), so we only need to read a subset of the proof (determined by the coin tosses). And in fact, constantly many queries,