Class Description

P^{NP[log^2]}: P With Log² NP Queries

Same as P^NP[log], except that now log² queries can be made.

The model-checking problem for a certain temporal logic is P^{NP[log^2]}-complete [Sch03].

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

Linked From

No class.