Class Description
VCk: Verification Class With A Circuit of Depth K
- For k = 0, VC0 is the class of compressible languages.
- For k = 1, VC1 is the class of languages that have local verification: they can be verified by testing only a small part of the instance. (Small means polynomial in the witness length and the log of the instance length.)
- For k ≥ 2, VCk is the class of languages that can be verified by a circuit of depth k, with size polynomial in the witness length and instance length.
VC0 ⊆ VCOR ⊆ VC1 ⊆ VC2 ⊆ VC3 …
Introduced in [HN06]; see there for formal definitions.
Linked From
VCor: Verification Class With OR
The class of languages that have verification presentable as the OR of m instances of SAT, each of size n. (m is the witness length of an instance and n is the instance length.)
Introduced in [HN06].
See also VCk.
More about...