Linked Questions

14
votes
1answer
719 views

Is Quasi-polynomial time in PSPACE?

I had done some search on this but I was not able to find an answer either way. Huck answered it fully. Thanks :)
2
votes
1answer
367 views

Complexity lower bound of finding the factorial of a number

I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read. Two similar problems, Matrix Multiplication and ...
8
votes
2answers
570 views

Is there a list of known problems?

Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us? [If not, can we make one? I know this is off ...
-2
votes
1answer
268 views

Finding research problem for PhD(TCS)? [closed]

I am a theoratical computer science PhD student. I am wanted some suggestion in how to find research problem for PhD research. I have supervisor and he has given me first problem. We had get progress ...
3
votes
0answers
269 views

Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ...
-2
votes
1answer
160 views

Evidence integer multiplication is in linear time?

After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...

15 30 50 per page
1
2