Skip to main content

Explore our questions

1 vote
2 answers
63 views

Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

0 votes
0 answers
9 views

Integration of analytic function

0 votes
0 answers
21 views

NP-completeness of Nested Flexible Machine Scheduling with summaric job completion time

17 votes
1 answer
467 views

Strongly Regular Graph and GI-Completeness

18 votes
4 answers
4k views

What would be the consequences of $\mathsf{PH=PSPACE}$?

-2 votes
0 answers
33 views

Big O of evaluating expression under RAM model

1 vote
0 answers
34 views

Clause Density for guaranteed Easy (2, 3) SAT Cases

2 votes
1 answer
132 views

Complexity of 2-coloring with extra constraints

4 votes
1 answer
85 views

Solving #SAT through TQBF

4 votes
0 answers
61 views

EXPSPACE-complete optimization problems

1 vote
2 answers
145 views

Use of transitive closure in proof of NC hierarchy collapse

12 votes
3 answers
509 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

5 votes
1 answer
124 views

How to prove that a problem is not smoothed-polynomial?

3 votes
0 answers
51 views

Complexity of minimizing the index of a subgroup of the free group

Browse more Questions