Abstract
Despite the interest in the complexity class MA, the randomized analog of NP, there are just a few known natural (promise)MAcomplete problems. The first such problem was found by Bravyi and Terhal (SIAM Journal of Computing 2009); this result was then followed by Crosson, Bacon and Brown (PRE 2010) and then by Bravyi (Quantum Information and Computation 2015). Surprisingly, each of these problems is either from or inspired by quantum computation. This fact makes it hard for classical complexity theorists to study these problems, and prevents potential progress, e.g., on the important question of derandomizing MA.
In this note we define two new natural combinatorial problems and we prove their MAcompleteness. The first problem, that we call approximatelyclean approximateconnectedcomponent (ACAC), gets as input a succinctly described graph, some of whose vertices are marked. The problem is to decide whether there is a connected component whose vertices are all unmarked, or the graph is far from having this property. The second problem, called SetCSP, generalizes in a novel way the standard constraint satisfaction problem (CSP) into constraints involving sets of strings.
Technically, our proof that SetCSP is MAcomplete is a fleshing out of an observation made in (Aharonov and Grilo, FOCS 2019), where it was noted that a restricted case of Bravyi and Terhal’s MA complete problem (namely, the uniform case) is already MA complete; and, moreover, that this restricted case can be stated using classical, combinatorial language. The fact that the first, arguably more natural, problem of ACAC is MAhard follows quite naturally from this proof as well; while containment of ACAC in MA is simple, based on the theory of random walks.
We notice that this work, along with a translation of the main result of Aharonov and Grilo to the SetCSP problem, implies that finding a gapamplification procedure for SetCSP (in the spirit of the gapamplification procedure introduced in Dinur’s PCP proof) would imply MA=NP. In fact, the problem of finding gapamplification for SetCSP is equivalent to the MA=NP problem. This provides an alternative new path towards the major problem of derandomizing MA. Deriving a similar statement regarding gap amplification of a natural restriction of $ACAC$ remains an open question.
BibTeX  Entry
@InProceedings{aharonov_et_al:LIPIcs.ITCS.2021.36,
author = {Dorit Aharonov and Alex B. Grilo},
title = {{Two Combinatorial MAComplete Problems}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {36:136:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13575},
URN = {urn:nbn:de:0030drops135754},
doi = {10.4230/LIPIcs.ITCS.2021.36},
annote = {Keywords: MerlinArthur proof systems, Constraint sastifation problem, Random walks}
}
Keywords: 

MerlinArthur proof systems, Constraint sastifation problem, Random walks 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 