Complexity Zoo:X - Revision history

Timeroot: Fixing XL and XNL, adding XNLP

2022-11-30T19:45:01Z

Fixing XL and XNL, adding XNLP

Lark1997: /* XNL: Fixed-Parameter Nondeterministic Logspace for Each Parameter */

2019-05-21T08:56:14Z

XNL: Fixed-Parameter Nondeterministic Logspace for Each Parameter

Timeroot: Adding XL and XNL.

2019-04-29T19:28:27Z

Adding XL and XNL.

Charles R Greathouse IV: /* XOR-MIP[2,1]: {{zcls|m|mipstar21|MIP[2,1]}} With 1-Bit Proofs */ fix links

2013-06-20T14:11:26Z

XOR-MIP*[2,1]: {{zcls|m|mipstar21|MIP*[2,1]}} With 1-Bit Proofs: fix links

Admin: 1 revision: Complexity zoo import.

2012-11-18T03:10:33Z

1 revision: Complexity zoo import.

New page

__NOTOC__
{{CZ-Letter-Menu|X}}

===== XOR-MIP*[2,1]: {{zcls|m|mipstar21|MIP*[2,1]}} With 1-Bit Proofs =====
Same as [[#mipstar21|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 [[zooref#cht04|[CHT+04]]], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.

XOR-MIP*[2,1] is contained in [[Complexity Zoo:N#nexp|NEXP]] [[zooref#cht04|[CHT+04]]].

XOR-MIP*[2,1] is contained in [[Complexity Zoo:Q#qip2|QIP[2]]] [[zooref#weh06|[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 [[zooref#df99|[DF99]]].

Contains [[#xpuniform|XPuniform]].

Strictly contains [[Complexity Zoo:F#fpt|FPT]] (by diagonalization).

----
===== XPuniform: Uniform [[#xp|XP]] =====
Same as [[#xp|XP]] except that the algorithm used must be the same for each k (though it can take k as input).

Defined in [[zooref#df99|[DF99]]].

@@ Line 14: / Line 14: @@
 ----
 ===== <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.
+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]].
@@ Line 24: / Line 24: @@
 ----
 ===== <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(<sup>f(k)</sup>+log(n)), by a nondeterministic Turing machine, 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 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]].
 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?

@@ Line 23: / Line 23: @@
 ----
-===== <span id="xl" style="color:red">XL</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(<sup>f(k)</sup>+log(n)), by a nondeterministic Turing machine, for some function f.  The algorithm used may depend on k.
@@ Line 32: / Line 32: @@
 ----
 ===== <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.

@@ Line 13: / Line 13: @@
 ----
 ===== <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.