# 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]: 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].