Skip to main content
Eric Allender's user avatar
Eric Allender's user avatar
Eric Allender's user avatar
Eric Allender
  • Member for 13 years, 9 months
  • Last seen this week
41 votes

Are the problems PRIMES, FACTORING known to be P-hard?

30 votes

Problems Between P and NPC

27 votes
Accepted

Is finding Logspace reductions harder than P reductions?

14 votes

Relativization with Respect to Non-Recursive Oracles

12 votes
Accepted

How stringent is the peer review process of ECCC exactly?

9 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

9 votes
Accepted

Is Circuit Minimization $P$-hard under logspace reductions?

8 votes

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

8 votes
Accepted

Fast algorithms for time bounded Kolmogorov complexity

7 votes
Accepted

What circuit depth is enough to compute a log-space complete problem?

7 votes

Algorithm for ranking members of a regular language?

7 votes

is SUBEXP contained within PSPACE?, NP?

6 votes

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

6 votes

Resource-bounded variant of Kolmogorov complexity

6 votes
Accepted

$\mathsf{TC^0}$-completeness and reductions

5 votes
Accepted

Reductions and projections in circuit complexity

4 votes

Circuit uniformities more restrictive than $DLOGTIME$

3 votes

Ruzzo-Simon-Tompa oracle access mechanism

3 votes

Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$