Linked Questions

131
votes
28answers
20k views

Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
61
votes
13answers
8k views

Open problems on the frontiers of TCS

In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment: I think we should distinguish between major open problems that are viewed ...
-1
votes
1answer
167 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-...
11
votes
2answers
1k views

Sources of open problems?

I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about! Thanks so much!...
19
votes
5answers
1k views

P with integer factorization oracle

I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$: ...
35
votes
3answers
3k views

Consequences of Factoring being in P?

Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a ...
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 ...
26
votes
4answers
1k views

What specific evidence is there for P = RP?

RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
-2
votes
1answer
269 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 ...
24
votes
4answers
8k views

Major unsolved problems in distributed systems?

Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain. Something like membership protocols, data ...
2
votes
1answer
368 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 ...
38
votes
7answers
5k views

Many-one reductions vs. Turing reductions to define NPC

Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
12
votes
3answers
6k views

What does research in theoretical computer science involve?

I am trying to understand what is involved in theoretical computer science research. What do theoretical computer scientists do? I know a significant time is spent on teaching, supervising graduate ...
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 :)

15 30 50 per page