Linked Questions
21 questions linked to/from Major unsolved problems in theoretical computer science?
141
votes
30
answers
24k
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? ...
62
votes
13
answers
9k
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 ...
42
votes
7
answers
6k
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?
- 1,648
39
votes
5
answers
1k
views
Is there a logic without induction that captures much of P?
The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ...
- 18.8k
41
votes
2
answers
2k
views
Are the problems PRIMES, FACTORING known to be P-hard?
Let PRIMES (a.k.a. primality testing) be the problem:
Given a natural number $n$, is $n$ a prime number?
Let FACTORING be the problem:
Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
- 411
26
votes
4
answers
10k
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 ...
- 447
37
votes
3
answers
4k
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 ...
- 6,695
30
votes
2
answers
6k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 793
19
votes
5
answers
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$:
...
- 22.4k
27
votes
4
answers
2k
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 ...
- 18.8k
7
votes
3
answers
5k
views
Polynomial Time Algorithm for Graph Isomorphism Testing [closed]
"Michael I. Trofimov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.
The paper is given in arXiv. The companion website gives a proof-of-concept ...
- 16.3k
25
votes
4
answers
2k
views
Best known deterministic time complexity lower bound for a natural problem in NP
This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time.
Looking at the comments under answer ...
- 4,001
13
votes
3
answers
8k
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 ...
22
votes
1
answer
2k
views
Is there a proof that addition is faster than multiplication?
The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition. Do we have a proof that ...
- 331
13
votes
2
answers
3k
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!...
- 151