Stack Exchange

Emil J

math.cas.cz/~jerabek

top accounts reputation activity favorites subscriptions
Top Questions
No questions with score of 5 or more
Top Answers
22
Is there a natural problem on the naturals that is NP-complete?
cstheory.stackexchange.com

21
Why are regular languages called “regular”?
cstheory.stackexchange.com

16
How can we express “$P=PSPACE$” as a first-order formula?
cstheory.stackexchange.com

15
Proofs in $S_{2}^{1}$
cstheory.stackexchange.com

13
Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$
cstheory.stackexchange.com

12
Computing the Mobius function
cstheory.stackexchange.com

12
Polynomial-time algorithms with huge exponent/constant
cstheory.stackexchange.com

12
Why valuations when defining FOL?
cstheory.stackexchange.com

10
About Closure under Resolution
cstheory.stackexchange.com

9
Can “$x(\lambda y.P\;)z$” be $\beta$-reduced?
cstheory.stackexchange.com

8
CFG parsing using $o(n^2)$ space
cstheory.stackexchange.com

8
Log-space reduction from Parity-L to CNOT circuits?
cstheory.stackexchange.com

8
Constructively efficient algorithms without efficient correctness and efficiency proof
cstheory.stackexchange.com

7
Complexity of finding the square root of a perfect square
cstheory.stackexchange.com

7
Other types of uniformity for circuits (incl. by small modifications)
cstheory.stackexchange.com

7
$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?
cstheory.stackexchange.com

7
Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?
cstheory.stackexchange.com

6
On $n$ dimensional manifolds and lattices
cstheory.stackexchange.com

6
are there fixed context sensitive grammars which are PSPACE complete?
cstheory.stackexchange.com

5
The complexity of comparing a power to some threshold
cstheory.stackexchange.com