Proof of `Clique Is in A[1]` (1st statement)

groundedproofs/Lax496464Proofs/WHierarchy/Reductions/CliqueLogic/CliqueMC.lean · lax-496464

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

p−Clique≤fptp−MC(Σ1)p-Clique ≤fpt p-MC(Σ_1). (G,k)↦(G,cliquek)(G, k) ↦ (G, clique_k) with cliquek=∃x0…∃xk−1⋀i<j<k(¬xi=xj∧Exixj)clique_k = ∃x_0 … ∃x_{k-1} ⋀_{i<j<k} (¬ x_i = x_j ∧ E x_i x_j) (the conjunction closed by x0=x0x_0 = x_0), for 1≤k≤n1 ≤ k ≤ n; k=0k = 0 goes to a fixed yes-instance and k>nk > n to a fixed no-instance. The new parameter is at most 10(k+1)210 (k + 1)², and the map is computed by an IMP+ program in O(∣x∣3)O(|x|³) steps.