Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

1 vote
0 answers
56 views

Is NLOGTIME self-low?

3 votes
1 answer
200 views

Relativized world in which P ≠ NP = coNP

4 votes
0 answers
95 views

$\mathsf{NL}$ vs. $\mathsf{AC}^1$

4 votes
2 answers
401 views

Random self reducibility and NP

-3 votes
0 answers
76 views

Relation between $NC^i$ and $L^i$

2 votes
0 answers
121 views

Is modular square roots in NC?

5 votes
1 answer
107 views

DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

43 votes
3 answers
7k views

P and NP classes explanation through lambda-calculus

0 votes
0 answers
91 views

Non-uniformity assumptions in circuit complexity

1 vote
0 answers
64 views

One way analogues of Logspace

2 votes
0 answers
95 views

Problems in $P^{PP}$

20 votes
4 answers
1k views

Parity and $AC^0$

9 votes
1 answer
455 views

Cobham's Result on Efficient Computations

0 votes
0 answers
66 views

On the Reductions of Functional complexity Classes

Browse more Questions