Skip to main content
added 22 characters in body
Source Link
Ryan Williams
  • 4.8k
  • 29
  • 38

First, it isn't "clear" that $BPP$ has no complete problems: if $TIME[2^{O(n)}]$ requires circuits of size $2^{\delta n}$ for some $\delta > 0$ then $P = BPP$, in which case $BPP$ certainly does have complete problems! (This is a famous result of Impagliazzo and Wigderson from 1998.) Also, $MA$ is not known to have complete problems, but again, under plausible circuit complexity assumptions, $NP = MA$ in which case all $NP$-complete problems are $MA$-complete too. (This is due to Klivans and van Melkebeek, and others who have weakened/changed the assumptions under which $NP=MA$ holds.) But yes, complete problems for $BPP$ and $MA$ are not currently known.

Secondly, the "promise" versions of these classes have do natural complete promise problems. (A promise problem is a pair $(\Pi_{YES}, \Pi_{NO})$ where $\Pi_{YES}, \Pi_{NO} \subseteq$ {$0,1$}$^n$, and $\Pi_{YES} \cap \Pi_{NO} = \emptyset$. The crucial point is that we do not necessarily have $\Pi_{YES} \cup \Pi_{NO} = $ {$0,1$}$^n$, so some inputs may not be considered at all in a promise problem.) For example, the following promise problem is complete for $Promise-BPP$:

Given a Boolean circuit $C$ with AND/OR/NOT gates and $n$ inputs, where you are promised that either every input $x \in $at least 2/3 of the inputs {$0,1$}$^n$$x \in \{0,1\}^n$ makes $C$ evaluate to $0$, or at least half2/3 of the inputs $x \in \{0,1\}^n$ make $C$ evaluate to $1$, determine which of the two is the case.

Not sure who first proved that this problem is complete, though in the literature itthis problem is sometimes known ascalled CAPP (for Circuit Approximation Probability Problem). One reference is Fortnow, "Comparing notions of full derandomization".

Similarly defined promise problems (with nondeterminism thrown in, naturally) are complete for $Promise-MA$.

First, it isn't "clear" that $BPP$ has no complete problems: if $TIME[2^{O(n)}]$ requires circuits of size $2^{\delta n}$ for some $\delta > 0$ then $P = BPP$, in which case $BPP$ certainly does have complete problems! (This is a famous result of Impagliazzo and Wigderson from 1998.) Also, $MA$ is not known to have complete problems, but again, under plausible circuit complexity assumptions, $NP = MA$ in which case all $NP$-complete problems are $MA$-complete too. (This is due to Klivans and van Melkebeek, and others who have weakened/changed the assumptions under which $NP=MA$ holds.) But yes, complete problems for $BPP$ and $MA$ are not currently known.

Secondly, the "promise" versions of these classes have do natural complete promise problems. (A promise problem is a pair $(\Pi_{YES}, \Pi_{NO})$ where $\Pi_{YES}, \Pi_{NO} \subseteq$ {$0,1$}$^n$, and $\Pi_{YES} \cap \Pi_{NO} = \emptyset$. The crucial point is that we do not necessarily have $\Pi_{YES} \cup \Pi_{NO} = $ {$0,1$}$^n$, so some inputs may not be considered at all in a promise problem.) For example, the following promise problem is complete for $Promise-BPP$:

Given a Boolean circuit $C$ with AND/OR/NOT gates and $n$ inputs, where you are promised that either every input $x \in $ {$0,1$}$^n$ makes $C$ evaluate to $0$, or at least half the inputs $x \in \{0,1\}^n$ make $C$ evaluate to $1$, determine which of the two is the case.

Not sure who first proved that this problem is complete, though in the literature it is sometimes known as CAPP (for Circuit Approximation Probability Problem). One reference is Fortnow, "Comparing notions of full derandomization".

Similarly defined promise problems (with nondeterminism thrown in, naturally) are complete for $Promise-MA$.

First, it isn't "clear" that $BPP$ has no complete problems: if $TIME[2^{O(n)}]$ requires circuits of size $2^{\delta n}$ for some $\delta > 0$ then $P = BPP$, in which case $BPP$ certainly does have complete problems! (This is a famous result of Impagliazzo and Wigderson from 1998.) Also, $MA$ is not known to have complete problems, but again, under plausible circuit complexity assumptions, $NP = MA$ in which case all $NP$-complete problems are $MA$-complete too. (This is due to Klivans and van Melkebeek, and others who have weakened/changed the assumptions under which $NP=MA$ holds.) But yes, complete problems for $BPP$ and $MA$ are not currently known.

Secondly, the "promise" versions of these classes have do natural complete promise problems. (A promise problem is a pair $(\Pi_{YES}, \Pi_{NO})$ where $\Pi_{YES}, \Pi_{NO} \subseteq$ {$0,1$}$^n$, and $\Pi_{YES} \cap \Pi_{NO} = \emptyset$. The crucial point is that we do not necessarily have $\Pi_{YES} \cup \Pi_{NO} = $ {$0,1$}$^n$, so some inputs may not be considered at all in a promise problem.) For example, the following promise problem is complete for $Promise-BPP$:

Given a Boolean circuit $C$ with AND/OR/NOT gates and $n$ inputs, where you are promised that either at least 2/3 of the inputs $x \in \{0,1\}^n$ makes $C$ evaluate to $0$, or at least 2/3 of the inputs $x \in \{0,1\}^n$ make $C$ evaluate to $1$, determine which of the two is the case.

Not sure who first proved that this problem is complete, though in the literature this problem is sometimes called CAPP (for Circuit Approximation Probability Problem). One reference is Fortnow, "Comparing notions of full derandomization".

Similarly defined promise problems (with nondeterminism thrown in, naturally) are complete for $Promise-MA$.

Source Link
Ryan Williams
  • 4.8k
  • 29
  • 38

First, it isn't "clear" that $BPP$ has no complete problems: if $TIME[2^{O(n)}]$ requires circuits of size $2^{\delta n}$ for some $\delta > 0$ then $P = BPP$, in which case $BPP$ certainly does have complete problems! (This is a famous result of Impagliazzo and Wigderson from 1998.) Also, $MA$ is not known to have complete problems, but again, under plausible circuit complexity assumptions, $NP = MA$ in which case all $NP$-complete problems are $MA$-complete too. (This is due to Klivans and van Melkebeek, and others who have weakened/changed the assumptions under which $NP=MA$ holds.) But yes, complete problems for $BPP$ and $MA$ are not currently known.

Secondly, the "promise" versions of these classes have do natural complete promise problems. (A promise problem is a pair $(\Pi_{YES}, \Pi_{NO})$ where $\Pi_{YES}, \Pi_{NO} \subseteq$ {$0,1$}$^n$, and $\Pi_{YES} \cap \Pi_{NO} = \emptyset$. The crucial point is that we do not necessarily have $\Pi_{YES} \cup \Pi_{NO} = $ {$0,1$}$^n$, so some inputs may not be considered at all in a promise problem.) For example, the following promise problem is complete for $Promise-BPP$:

Given a Boolean circuit $C$ with AND/OR/NOT gates and $n$ inputs, where you are promised that either every input $x \in $ {$0,1$}$^n$ makes $C$ evaluate to $0$, or at least half the inputs $x \in \{0,1\}^n$ make $C$ evaluate to $1$, determine which of the two is the case.

Not sure who first proved that this problem is complete, though in the literature it is sometimes known as CAPP (for Circuit Approximation Probability Problem). One reference is Fortnow, "Comparing notions of full derandomization".

Similarly defined promise problems (with nondeterminism thrown in, naturally) are complete for $Promise-MA$.