Difference between revisions of "Complexity Zoo:X"
(Fixing XL and XNL, adding XNLP) |
|||
| Line 14: | Line 14: | ||
---- | ---- | ||
===== <span id="xl" style="color:red">XL</span>: Fixed-Parameter Logspace for Each Parameter ===== | ===== <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( | + | 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|XP]], as [[Complexity Zoo:L#l|L]] is to [[Complexity Zoo:P#p|P]]. | Analogous to [[#xp|XP]], as [[Complexity Zoo:L#l|L]] is to [[Complexity Zoo:P#p|P]]. | ||
| Line 24: | Line 24: | ||
---- | ---- | ||
===== <span id="xnl" style="color:red">XNL</span>: Fixed-Parameter Nondeterministic Logspace for Each Parameter ===== | ===== <span id="xnl" style="color:red">XNL</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( | + | 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|XP]], as [[Complexity Zoo:NL#nl|NL]] is to [[Complexity Zoo:P#p|P]]. Nondeterministic version of [[#xl|XL]]. | 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? | 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="xnlp" style="color:red">XNLP</span>: Fixed-Parameter Nondeterministic Logspace and Polytime 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)) and time O(f(k) n<sup>c</sup>), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k. | ||
| + | |||
| + | Contained in [[#xnl|XNL]], which has the same space restriction but allows runtimes of O(n<sup>f(k)</sup>). | ||
| + | |||
| + | Without the nondeterminism, this would also be contained in [[F#fpt|FPT]], as the runtime is fixed-parameter tractable. But, it is nondeterministic. | ||
| + | |||
| + | Reference: [https://arxiv.org/abs/2201.13119] | ||
Latest revision as of 19:45, 30 November 2022
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 - XPuniform
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]
XNL: 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?
XNLP: Fixed-Parameter Nondeterministic Logspace and Polytime 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)) and time O(f(k) nc), by a nondeterministic Turing machine, for some function f. The algorithm used may depend on k.
Contained in XNL, which has the same space restriction but allows runtimes of O(nf(k)).
Without the nondeterminism, this would also be contained in FPT, as the runtime is fixed-parameter tractable. But, it is nondeterministic.
Reference: [2]
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 XPuniform.
Strictly contains FPT (by diagonalization).
XPuniform: 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].