Linked Questions

141 votes
30 answers
25k 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 ...
43 votes
7 answers
7k 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?
Matthias's user avatar
  • 1,668
39 votes
5 answers
2k 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 ...
András Salamon's user avatar
42 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$, ...
k m's user avatar
  • 421
27 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 ...
zengr's user avatar
  • 457
38 votes
3 answers
5k 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 ...
Giorgio Camerani's user avatar
31 votes
2 answers
7k views

What would be the consequences of factoring being NP-complete?

Are there any references covering this?
txwikinger's user avatar
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$: ...
Marzio De Biasi's user avatar
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 ...
András Salamon's user avatar
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 ...
Sadeq Dousti's user avatar
  • 16.5k
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 ...
Anonymous's user avatar
  • 4,041
14 votes
3 answers
9k 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 ...
undergrad cs student's user avatar
14 votes
2 answers
4k 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!...
Jake Shellman's user avatar
22 votes
1 answer
3k 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 ...
Hooman's user avatar
  • 331

15 30 50 per page