Skip to main content
The 2024 Developer Survey results are live! See the results

New answers tagged

5 votes
Accepted

References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$

Here are some papers that have results similar to the ones you ask about. Ronald V. Book, On Languages Accepted in Polynomial Time, SIAM J. Comput. 1, 1972, pp. 281-287. In this paper, we find Theorem ...
Eric Allender's user avatar
3 votes
Accepted

Solving #SAT through TQBF

Let $\phi$ be a CNF formula. I'll show how to express a TQBF formula of polynomial size for your problem. In particular, let $\psi_i(t,j)$ be a formula that is true if there are at most $j$ values $x$...
D.W.'s user avatar
  • 12.2k
9 votes

A split-consistency property of a formal language

We discussed your question with @M.Monet in the case of regular languages. It turns out that, unless we're mistaken, your condition is precisely equivalent to saying that the language is recognized by ...
a3nm's user avatar
  • 9,667

Top 50 recent answers are included