Two combinatorial MA-complete problems
summary
Two new combinatorial problems are shown MA-complete: SetCSP is MA-hard for inverse-polynomial ε, and an implicit-graph problem ACAC is in MA via random-walk verification. SetCSP generalizes CSPs to sets of strings, uses reversible circuits and a history-set construction that forces all random coins to appear, and encodes MA verification. A polynomial-time reduction maps SetCSP to an implicit graph where satisfiable instances yield an unmarked connected component and unsatisfiable ones yield many marked vertices or high expansion.
AI-written summary · about