Class Description

PNP[log^2]: P With Log2 NP Queries

Same as PNP[log], except that now log2 queries can be made.

The model-checking problem for a certain temporal logic is PNP[log^2]-complete [Sch03].

For all k ≥ 1, P with logk adaptive queries to NP coincides with P with logk−1 rounds of (polynomially many) nonadaptive queries [CS92].

Linked From

No class.