6
$\begingroup$

I'm reading this paper: Quadratic Span Programs and Succinct NIZKs without PCP
Is QAP NP-complete? as same as QSP?

$\endgroup$

1 Answer 1

8
$\begingroup$

QAP, like QSP, are a characterization of NP. They naturally capture arithmetic programs. Their advantage over QSP is that they lead to more efficient SNARGs for statements whose verification procedure is compactly represented by an arithmetic circuit. They have at least the same power, and you can represent the verification algorithm of arbitrary NP languages (hence also NP-complete languages) using them. Note that they are a computation model, not a language, so it does not mean anything to say that QAPs (or QSPs) are NP-complete - but they do capture all of NP.

$\endgroup$
3
  • $\begingroup$ Would it be correct to say that the language QAP-SAT $ = \{ (Q, x) | Q \text{ is a QAP and there exists a witness $w$ such that $x$ and $w$ satisfy $Q$ } \}$ is NP-complete? Satisfying $Q$ with $x$ and $w$ means to fulfill the divisibility condition as per GGPR13. Every language $L \in NP$ is represented by a QAP $Q$ such that $x \in L \iff (Q, f(x)) \in $ QAP-SAT. I am asking because I have read that R1CS and QAP are NP-complete, but, as you point out, they are computational models not languages. So, would that language QAP-SAT be what people are referring to when stating such things? $\endgroup$
    – cadaniluk
    Commented Sep 13, 2021 at 21:32
  • $\begingroup$ ($x$ is meant to represent the input variables, $w$ is meant to represent the input variables plus "the rest".) I thought about whether a language like $\{ Q | \text{$Q$ is a QAP and there exist $x, w$ such that they satisfy $Q$} \}$ is NP-complete, but even if it was, this is not how it is done with preprocessing zk-SNARKs, is it? One QAP models a language $L \in NP$, not just a single input $x \in L$, otherwise the QAP would change for every new input $x$, which would be terrible. $\endgroup$
    – cadaniluk
    Commented Sep 13, 2021 at 21:33
  • $\begingroup$ For example, Madars Virza writes in his PhD thesis that the "QAP satisfiability problem is NP-complete." What does the language that describes the "QAP satisfiability problem" look like formally? Is it the QAP-SAT I described in my first comment? $\endgroup$
    – cadaniluk
    Commented Sep 13, 2021 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.