6
$\begingroup$

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

$\endgroup$
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
    Sep 13 '21 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
    Sep 13 '21 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
    Sep 13 '21 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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