Given the circuit and a setting of a, b, c, d, does the lamp light?

Work through the gates in order. Each gate reads wires that are already settled, so one pass does it: five gates, five steps. Double the circuit and you double the work.

Circuit Value is P-complete. Any polynomial-time program, unrolled over its running time, becomes a circuit like this one, so a fast parallel algorithm for this problem would give one for everything in P.

Time

one step per gate: O(size)

Space

one bit per wire

Complete problem

Circuit Value (CVP)

Is there any setting of a, b, c, d that lights the lamp?

Nobody hands you the input now. If someone proposes one, checking it is the P problem above. Finding one is another matter: the best known general methods still try exponentially many of the 2ⁿ settings in the worst case. Click any setting to check it, or let the search run.

Each check costs 5 gate evaluations. The search may cost up to 16 checks.

Check

polynomial, given the certificate

Find

2ⁿ tries by brute force

Complete problem

Circuit SAT

Two players take turns setting a, b, c, d. Can the player who wants the lamp lit always win?

The quantifiers say who sets each input. ∃ (“there exists”) marks an input chosen by the player who wants the lamp lit. ∀ (“for all”) marks an input chosen by the player who wants it dark. They move in order a, b, c, d, and each sees the earlier moves.

So ∃a ∀b ∃c ∀d reads: there is a choice of a such that, whatever b is, there is a choice of c such that, whatever d is, the lamp lights. That is the same as saying the lit player has a strategy that wins against every reply. Click a quantifier to hand that input to the other player.

The tree has 2ⁿ leaves, so the walk can take exponential time. But a depth-first walk only ever holds one path from root to leaf: n frames. When one branch already settles a node, the walk skips the other (dashed). The same memory gets reused for every path, which is why the whole class is about space.

Time

up to 2ⁿ leaves

Space

n stack frames

Complete problem

Quantified SAT (TQBF)

In a game with no move limit, can you force the lamp to light?

You own a and b. Your opponent owns c and d. On each turn the player to move must flip one of their own bits, and whoever's flip lights the lamp wins. Positions can repeat, so play can go on forever. Depth-first search no longer works, because a path can be endless.

Instead, label every position, working backwards from the lit ones. First mark the positions where you can light the lamp now. Then mark those where every opponent reply leads into an already-marked position. Repeat until nothing changes. Whatever stays unmarked is a draw.

Rows are ab and columns are cd, in Gray-code order like a Karnaugh map, so neighboring cells differ by one flip.

Time

polynomial in 2 × 2ⁿ positions

Space

a label for every position

Complete problem

Formula games (Stockmeyer–Chandra), generalized chess

Put 2^k lamps in a circle. Every tick, the circuit sets each lamp from itself and its neighbors. Do all the lamps eventually go out?

Each lamp is on or off. On every tick, all lamps update at once. Each lamp feeds four values into the circuit: the lamp to its left as a, itself as b, the lamp to its right as c, and the one after that as d. The circuit’s output is the lamp’s new state. In the diagram below, the top row is the starting circle cut open and laid flat, and each row under it is the next tick.

Why this is a step up: the question only takes the circuit and the number k to write down, but the circle has 2^k lamps, so just holding its current state takes exponential memory. There are 2^2k possible on/off patterns, so the lamps can keep changing for an enormous time before any pattern repeats. The decider keeps two copies of the circle and watches for a repeat. Either every lamp goes out, or an earlier pattern comes back, which means the circle loops forever and never goes dark. Click a cell in the diagram to load its four inputs into the circuit.

On/off lamps with a fixed four-lamp neighborhood are a toy. Give each lamp a few more states and the rule a bigger circuit, and the circle can simulate any machine with 2^k memory cells. That makes the general question EXPSPACE-complete. With k lamps instead of 2^k, the same question is PSPACE-complete.

Time

up to 2^2k ticks

Space

two copies of the circle: 2 × 2^k bits

Complete problem

Acceptance by 2ⁿ-space machines; regex equivalence with squaring