Questions: Descriptive Complexity: Expressing Complexity in Logic

Question 1

A researcher wants to prove that the 3-colorability problem (deciding if a graph can be colored with 3 colors such that no two adjacent vertices share a color) is in NP. According to Fagin's theorem, which approach is equivalent to exhibiting a polynomial-time nondeterministic algorithm?

• A. Showing 3-colorability reduces to an existing problem known to be in NP
• B. Writing an existential second-order sentence that is true of a graph if and only if it is 3-colorable
• C. Writing an FO + LFP sentence that is true of a graph if and only if it is 3-colorable
• D. Showing the problem can be decided in polynomial space

Answer: (B)

Fagin's theorem states that NP equals exactly the class of problems expressible as existential second-order (ESO) sentences. Writing 'there exist three color classes such that no two adjacent vertices share a class' is an ESO sentence (it existentially quantifies over three relations), and this directly witnesses NP membership. FO + LFP (option C) characterizes P, not NP — using it would show the problem is in P, which is a stronger claim. PSPACE corresponds to full second-order logic. The logical and computational characterizations are provably equivalent.

Question 2

Which statement correctly describes the significance of P = FO + LFP (first-order logic with least fixed-point operator)?

• A. It means every problem solvable in polynomial time can be described by a pure first-order sentence
• B. It means polynomial-time computation is equivalent to iterative fixed-point reasoning expressible in first-order logic, on ordered structures
• C. It means the least fixed-point operator adds exponential expressive power over first-order logic
• D. It means all polynomial-time algorithms can be replaced by logical inference without any fixed-point iteration

Answer: (B)

P = FO + LFP (on ordered structures) says that every polynomial-time decidable property can be expressed as a first-order sentence augmented with a least fixed-point operator, and conversely, every such sentence defines a polynomial-time property. The LFP operator builds up a relation iteratively — like computing reachability by repeatedly adding edges — and terminates in at most n iterations (polynomial). Pure first-order logic (option A) is far weaker than P; it cannot express reachability, for instance. The result holds on ordered structures, which is an important technical caveat.

Question 3

Fagin's theorem characterizes NP using existential second-order logic without reference to any specific machine model or running time.

• T. True
• F. False

Answer: True

This machine-independence is the theorem's most striking feature. Fagin's theorem says a property is in NP if and only if it is expressible as an ESO sentence — no mention of Turing machines, nondeterminism, or polynomial time appears in the logical characterization. The logical definition captures exactly the same class of problems as the computational one, from a completely different starting point. This means you can prove NP membership by writing a formula, not by designing an algorithm, and the two proofs are provably equivalent.

Question 4

If P ≠ NP, then every problem in NP but not in P can be expressed in existential second-order logic but not in FO + LFP.

• T. True
• F. False

Answer: True

This is a direct consequence of the logical characterizations: P = FO + LFP and NP = ESO. If P ≠ NP, then these complexity classes are genuinely different, which means FO + LFP and ESO must be expressively different — there must be properties expressible in ESO but not in FO + LFP. Any NP-complete problem that is not in P (assuming P ≠ NP) would be an example: expressible as an ESO sentence, but no FO + LFP sentence can express it. This reformulates the P vs. NP problem as a question about logical expressive power.

Question 5

Explain why the equivalence NP = ESO (Fagin's theorem) is considered surprising, and what it reveals about the relationship between nondeterminism and logic.

Model answer: It's surprising because NP and ESO were defined through completely different frameworks — NP via nondeterministic Turing machines and polynomial time bounds, ESO via quantifier syntax and logical expressibility — with no obvious reason to expect them to coincide. The equivalence reveals that nondeterminism, which computationally means 'guess a certificate and verify it,' is logically captured exactly by existential quantification over relations. Guessing a coloring is equivalent to asserting 'there exist color classes such that…' — the logical and computational acts are the same thing described in different languages. This connection opens the possibility of proving complexity separations using logical tools like quantifier elimination.

The deeper philosophical point is that complexity classes may not be arbitrary computational artifacts but natural logical categories — the problems you can 'describe' in a given logical language are exactly the problems you can 'decide' with a corresponding computational resource. This suggests that the difficulty of P vs. NP might be understood as a question about why certain logical languages can't express certain properties, even though we don't yet know how to prove such separations.