# Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness:

$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}|$ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.

You can assume that the verifier has random access to the graph adjacency matrix in $O(1)$ time.

Examples for $EasyVer$ problems will be $VC, Clique, IS$ and $Steiner Tree$.

Also, many packing and problems, $triangle-packing$, $k-path-packing$, or in general $H-packing$ for a graph $H$ with constant treewidth, are all in $EasyVer$.

Problems which aren't in (i.e. require more extensive interaction with the input) are also easily found: $VC, DominatingSet, FVS$(Feedback Vertex Set).

In order to get a sense of how $EasyVer$ relates to known complexity classes it would be useful to have a list of problem it contains.

Which other NP-complete problem (or even better, problem classes) can be verified in $poly(k)$ time, where $k$ is the size of the problem witness?

• Is the verifier a word RAM? $\:$ If no, how do you show that $Clique$ and $IS$ are in $EasyVer$? $\;\;$ Even if the machine allows Random Access with the target provided as a given slice of a tape, I don't see any way, other than the verifier being a word RAM, to make verification run in less than $\:k\cdot \Omega(\log(\log(|V|)))\:$ time. $\;\;\;\;\;$ – user6973 Mar 8 '14 at 20:48
• @RickyDemer - you can assume that the verifier has random access to the graph adjacency table, I've edited the question. – R B Mar 8 '14 at 20:58
• That doesn't resolve my issue, since I don't see a way for anything other than a word RAM to even select the target entry (for random access) in less than $\Omega(\log(\log(|V|)))$ time. $\;$ – user6973 Mar 8 '14 at 21:02
• @RickyDemer, perhaps we should then go back to my previuous question, where I asked what's the right way to define this class: cstheory.stackexchange.com/questions/21409/…. – R B Mar 8 '14 at 21:04
• One could specify that the verifier receives the adjacency matrix of a vertex-induced subgraph, but not the rest of the original adjacency matrix. $\;$ – user6973 Mar 8 '14 at 21:09

If I get it right, you are interested in those parameterized problems that can be verified by a bounded-time NTM (running in time $f(k)$ for some function of the parameter). Up to fpt-reduction, these are precisely the problems in the class $W[1]$, see "On the parameterized complexity of short computation and factorization" by Cai, Chen, Downey and Fellows.
• That's why I wrote "up to fpt-reduction", as $W[1]$ can defined as the class of problems fpt-reducible to Short Nondeterministic Turing machine Computation. If you focus on bounded-time verification, it may be possible to define a variant of $W[1]$ using a different type of reduction... – Super8 Mar 9 '14 at 15:32