# Difference between revisions of "Complexity Zoo:X"

(Adding XL and XNL.) |
|||

Line 13: | Line 13: | ||

---- | ---- | ||

+ | ===== <span id="xl" style="color:red">XL</span>: Fixed-Parameter Logspace for Each Parameter ===== | ||

+ | The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(<sup>f(k)</sup>+log(n)) for some function f. The algorithm used may depend on k. | ||

+ | Analogous to [[#xp|XP]], as [[Complexity Zoo:L#l|L]] is to [[Complexity Zoo:P#p|P]]. | ||

+ | |||

+ | A natural XL complete problem is p-MDFA-ACCEPTANCE: Given a finite two-way deterministic automation A with k heads, and given a string x, does A accept x? | ||

+ | |||

+ | Reference: [https://eccc.weizmann.ac.il/report/2012/150/download/] | ||

+ | |||

+ | ---- | ||

+ | ===== <span id="xl" style="color:red">XL</span>: Fixed-Parameter Nondeterministic Logspace for Each Parameter ===== | ||

+ | The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(<sup>f(k)</sup>+log(n)), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k. | ||

+ | |||

+ | Analogous to [[#xp|XP]], as [[Complexity Zoo:NL#nl|NL]] is to [[Complexity Zoo:P#p|P]]. Nondeterministic version of [[#xl|XL]]. | ||

+ | |||

+ | A natural XNL complete problem is p-MNFA-ACCEPTANCE: Given a finite two-way nondeterministic automation A with k heads, and given a string x, does A accept x? | ||

+ | |||

+ | |||

+ | ---- | ||

===== <span id="xp" style="color:red">XP</span>: Fixed-Parameter Tractable for Each Parameter ===== | ===== <span id="xp" style="color:red">XP</span>: 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|<sup>f(k)</sup>) for some function f. The algorithm used may depend on k. | The class of decision problems of the form (x,k) (k a parameter) that are solvable in time O(|x|<sup>f(k)</sup>) for some function f. The algorithm used may depend on k. |

## Revision as of 19:28, 29 April 2019

*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]

##### XL: Fixed-Parameter Logspace for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(^{f(k)}+log(n)) for some function f. The algorithm used may depend on k.

Analogous to XP, as L is to P.

A natural XL complete problem is p-MDFA-ACCEPTANCE: Given a finite two-way deterministic automation A with k heads, and given a string x, does A accept x?

Reference: [1]

##### XL: Fixed-Parameter Nondeterministic Logspace for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in space O(^{f(k)}+log(n)), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k.

Analogous to XP, as NL is to P. Nondeterministic version of XL.

A natural XNL complete problem is p-MNFA-ACCEPTANCE: Given a finite two-way nondeterministic automation A with k heads, and given a string x, does A accept x?

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