Complexity Zoo:X

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

XOR-MIP*[2,1] - XL - XNL - XP - XP_uniform

XOR-MIP*[2,1]: MIP*[2,1] With 1-Bit Proofs

Same as MIP*[2,1], but with the further restriction that both provers send only a single bit to the verifier, and the verifier's output is a function of the exclusive-OR of those bits. There should exist 0<a<b<1 such that if the answer is "yes", then for some responses of the provers the verifier accepts with probability at least b, while if the answer is "no", then for all responses of the provers the verifier accepts with probability at most a.

Defined by [CHT+04], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.

XOR-MIP*[2,1] is contained in NEXP [CHT+04].

XOR-MIP*[2,1] is contained in QIP[2] [Weh06]

---

XP: Fixed-Parameter Tractable for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in time O(|x|^f(k)) for some function f. The algorithm used may depend on k.

Defined in [DF99].

Contains XP_uniform.

Strictly contains FPT (by diagonalization).

---

XP_uniform: Uniform XP

Same as XP except that the algorithm used must be the same for each k (though it can take k as input).

Defined in [DF99].