Skip to main content

Independent gates and remediation

Score CA1–CA6 separately: 0 absent/invalid; 1 assisted or materially incomplete; 2 independently correct with assumptions and checks; 3 also adapts to a changed case and defends limitations. Every gate requires at least 2. The reviewer key is for after an attempt. Averages cannot hide a missing reduction implication or invalid guarantee.

  • CA1: define decision/search/optimization variants of cover; specify encoded input and certificate checking cost. Explain why verifying a cover does not prove minimality.
  • CA2: reduce Independent Set to Vertex Cover on an n-vertex graph, including thresholds, both implications and polynomial construction cost. Explain the direction needed to establish target hardness.
  • CA3: reconstruct the 3-SAT-to-Independent-Set occurrence construction, size bound and both directions. Identify the theorem taken as given, then explain why decision Vertex Cover is NP-complete and optimization is NP-hard.
  • CA4: prove the maximal-matching two-approximation, including cover feasibility and a matching lower bound. Give a weighted counterexample and distinguish maximal from maximum.
  • CA5: implement the three lab contracts, pass fresh-extraction checks, and compare exact/approximate results on a triangle, star and changed graph. Explain the input guard, exponential work and why small exhaustive tests do not prove a general guarantee.
  • CA6: submit the solver-selection appendix, independently defend a changed threshold or objective, and distinguish a feasible incumbent, proven optimum and unresolved search. Explain the n-versus-k parameterized branching bound.

Preserve help, attempted proof, correction, evidence paths and reviewer status. After 7–14 days redo one weak proof and one implementation/contract case with changed inputs without the key. Label solo results self-assessed; independent curriculum review remains pending.

Language and computational limits​

The required automata/computability bridge supplies original lessons, a runnable experiment, selective MIT notes and AC1–AC4. All four gates must reach 2 independently in addition to CA1–CA6. Its additional 20–30 hours are included in the revised 45–65-hour module total.