New answers tagged complexity-classes
1
Many answers to this post, are also answer to this one, although the original question is different. All of the answers to this post are only conjectures though, it even seems there are standalone conjectures, i.e. they don't seem to rely on the usual bigger conjectures ($P \neq NP$)
Here is a list of problems taken from this post :
The best algorithm for $...
0
Per my comments above, here's a reduction that I think shows the problem to be PSPACE-hard (and presumably complete). Let $[n]$ be the graph with $n+1$ nodes, numbered $n\ldots 0$, with a link from node $i+1$ to $i$ for all $0\leq i\lt n$, all nodes other than $0$ marked for A, node $0$ marked for B, and the chit initially pleased on $n$. (All edges here ...
4
For many years researchers have studied pebbling problems and emptiness/reachability problems. Some of these problems have known unconditional resource lower bounds.
Such a problem $X$ is typically shown to have unconditional time complexity lower bounds by reducing the simulation of an $n^k$-time bounded Turing machine on a given input to an instance of $...
8
This is coNP-hard even if $B$ is also acyclic.
Let $D = \bigvee_{i=1}^m T_i$ be a DNF on variables $x_1, \dots, x_n$. We can easily contruct an NFA $B$ accepting exactly the satisfying assignment of $D$, that is, the words $w \in \{0,1\}^n$ such that the assignment $a$ defined as $a(x_i) = w_i$ satisfies $D$.
To do this, you build an automaton $B_i$ with $...
3
Well, here are a couple of observations. There's a famous PRG by Nisan that fools $\mathsf{BPL}$-type algorithms with seed length $O(\log^2 n)$. Given two-way access to the seed, Nisan's PRG can be computed in space $O(\log n)$. Therefore, every language in $\mathsf{BPL}$ can be decided by a $\mathsf{BP}^*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)...
Top 50 recent answers are included
