I'm reading this paper: Quadratic Span Programs and Succinct NIZKs without PCP
Is QAP NP-complete? as same as QSP?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Apr 5, 2019 at 11:39
-
$\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$ 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$ 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$ Sep 13, 2021 at 21:48