Class Description

VC_k: Verification Class With A Circuit of Depth K

For k = 0, VC₀ is the class of compressible languages.
For k = 1, VC₁ 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, VC_k 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.

VC₀ ⊆ VC_OR ⊆ VC₁ ⊆ VC₂ ⊆ VC₃ …

Introduced in [HN06]; see there for formal definitions.

Linked From

VC_or: 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].

Class Description

VCk: Verification Class With A Circuit of Depth K

Linked From

VCor: Verification Class With OR

VC_k: Verification Class With A Circuit of Depth K

VC_or: Verification Class With OR