# Tag Info

15

Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a decision tree of size $O(s)$, which can be implemented as an $O(s)$-size formula by replacing each query node with $(p\land\cdots)\lor(\neg p\land\cdots)$. It suffices to observe that there ...

6

Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ P / poly, then EXP^NP would be equal to EXP... We also know that if NEXP ⊆ P/poly, then NEXP = MA. Nevertheless, we do know that EXP^NP^NP is not in P/Poly.

6

The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $NEXP\not\subset P/poly$. It indicates to me that either we are missing something trivial which would separate $NEXP$ from $P/poly$ or (remotely plausibly) ...

4

Suppose $x \in \{0,\dots,2n\}$. Then we have $((2n)^2 - n) + x$ is square if and only if $x=n$. This is easily seen to imply that the square function is complete for $\mathrm{TC}^0$ under $\mathrm{AC}^0$ Turing reductions.

3

Edit: Oops, my intuition was wrong here! You can even get a deterministic algorithm from Emil's argument, by following Lemma 6.1 from Chen, Jin and myself (STOC 2020). That is, given any set P and N you can construct a circuit of size O(n log n) as desired in deterministic polynomial time.

3

Theorem 1. The problem in the post is NP-complete. Proof. MIN DNF is the following special case of the problem in the post: Given a truth table $T$ and integer $k$, is there a DNF of size at most $k$ whose truth table is $T$? MIN DNF is known to be NP-complete (see [1] and works cited by it). Since the problem in the post generalizes MIN DNF, the problem ...

2

The answer to the question is yes, assuming that (for all large $k$) $k$-SUM is not in $\text{DTIME}(n^{o(k)})$. It also follows (by a result of Patrascu and Williams) that the answer is yes assuming the ETH holds. The proof reuses the classical technique from the classical proof that, if any unary language is NP-hard, then P=NP. Definitions The question: ...

1

After re-reading Barrington et al., it seems that the case of $CC^0$ can be handled by using "group quantifiers", which allow for quantifiers to act over finite groups (i.e. $\mathbb{Z}/m\mathbb{Z}$) directly, while still using a binary representation under the hood so that the original definition of $DLOGTIME$-uniformity can still be used. With ...

1

My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, this generalizes to classical models as well. See Theorem 69 of Troy Lee and Adi Shraibman's survey [LS09], available, e.g., at this address. [BCW98] Buhrman, ...

Only top voted, non community-wiki answers of a minimum length are eligible