Class Description

VCk: Verification Class With A Circuit of Depth K

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...