Search Results

If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. Whil …

I will give two upper bounds. Let $A$ and $B$ be the sets given to Alice and Bob, respectively, and put $a=|A|$, $b=|B|$, $c=|A\cap B|$. First, there is a randomized protocol that, given $d>0$ and $ …

For a fixed alphabet $\Sigma$, the blow-up is at most polynomial. First, given a regular expression $r$, it is straightforward to construct an expression $\tilde r$ using the operators $a\in\Sigma$, $ …

Tseitin tautologies are unsatisfiable systems of linear equations over $\mathbb F_2$, and as such they can be refuted just by summing all the equations together (possibly after reconstructing the equa …

Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe: Lemma. For any NFA $A$ with $n$ states, the following ar …

By Proposition 13 in Benedikt and Hrushovski, the theory of finite fields has nonelementary complexity (it is harder than $k$-times iterated exponential time for all constants $k$). Apparently, the th …

Base conversion can be done in time $O(M(n)\log n)$, where $M(n)$ is a bound on the time complexity of multiplication of two $n$-bit integers. (We assume that $M(n)$ satisfies usual regularity conditi …

The revised conjecture is true, even under relaxed constraints on $S$ and $t$—they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ i …

Yes, any unsatisfiable Horn CNF has a tree-like resolution refutation with a linear number of clauses. Consider the standard poly-time Horn-SAT algorithm, which works as follows. First, set all variab …

I’ll comment on why a relation as in the question $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$ (for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can. The first ob …

(This is shameless self-promotion.) If you don’t mind either assuming the generalized Riemann hypothesis (for $L$-functions of quadratic Dirichlet characters) or using randomized polynomial time, then …

I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful …

The LP in question is a maximization over a bounded polytope, hence the optimal value is attained at a vertex of the polytope. Moreover, any vertex can be described as a unique solution of a system of …

$\def\M#1{\mathrm{MOD}_{#1}}\def\F#1{\mathbb F_{#1}}$I don’t know of a reference, but here is one way how to prove the result. I’ll do it in three stages, each using one new idea: (1) multilinear expa …

Since lower elementary functions are computable in time $2^{O(n)}$ (and space $O(n)$), the set of corresponding decision problems is unlikely to include NP, or even just $\mathrm{NTIME}(n^{1+\epsilon} …