Class Description

CL#P: Cluster Sharp-P

The class of #P function problems such that some underlying NP machine ${\displaystyle M}$ witnessing membership in #P has"clustered" accepting paths. That is:

• There exists a polynomial ${\displaystyle p}$ such that each computation path of ${\displaystyle M}$ on each input ${\displaystyle x}$ is exactly ${\displaystyle p(|x|)}$ bits long.
• There is a length-respecting total order ${\displaystyle A}$ having polynomial-time computable adjacency checks on the computation paths of ${\displaystyle M}$.
• The accepting paths of ${\displaystyle M}$ on any input ${\displaystyle x}$ are contiguous with respect to ${\displaystyle A}$.

Defined in [HHK+05].

Linked From

No class.