# Is Quadratic Arithmetic Program NP-complete?

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

• 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? Sep 13 '21 at 21:32
• ($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. Sep 13 '21 at 21:33