1
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ 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. $\;\;\;\;\;$ $\endgroup$
    – user6973
    Mar 8, 2014 at 20:48
  • $\begingroup$ @RickyDemer - you can assume that the verifier has random access to the graph adjacency table, I've edited the question. $\endgroup$
    – R B
    Mar 8, 2014 at 20:58
  • $\begingroup$ 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. $\;$ $\endgroup$
    – user6973
    Mar 8, 2014 at 21:02
  • $\begingroup$ @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/…. $\endgroup$
    – R B
    Mar 8, 2014 at 21:04
  • $\begingroup$ One could specify that the verifier receives the adjacency matrix of a vertex-induced subgraph, but not the rest of the original adjacency matrix. $\;$ $\endgroup$
    – user6973
    Mar 8, 2014 at 21:09

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not sure I understand your answer. FVS for example is even FPT, but it doesn't seem you can verify a feedback set without looking at all of the graph. $\endgroup$
    – R B
    Mar 9, 2014 at 15:23
  • $\begingroup$ 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... $\endgroup$
    – Super8
    Mar 9, 2014 at 15:32

Your Answer

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

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