Most Popular
1500 questions
42
votes
2 answers
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$, does $n$ have a factor $d$ with $1 < d < m$?
Is it…
k m
- 421
- 3
- 3
42
votes
23 answers
What hierarchies and/or hierarchy theorems do you know?
I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, from theology and sociology to biology and…
chazisop
- 3,796
- 2
- 29
- 37
42
votes
3 answers
Is the integer factorization problem harder than RSA factorization: $n = pq$?
This is a cross-post from math.stackexchange.
Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $n = \prod_{i=0}^{k} p_{i}^{e_i}.$
Let RSA denote…
user17
42
votes
4 answers
Single author papers against my advisor's will?
I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor.
My advisor is not involved in my research projects at all. In particular, I have come up with all of my paper ideas, and…
anonymous3724
- 429
- 4
- 3
42
votes
5 answers
What would you advise someone who wants to do research as a hobby?
I love doing TCS in my spare time. Lately I have been trying to do some research as a hobby.
I'm looking for some extra input from people who do this full-time:
Do you think it is possible to do this "just for fun"? I have no intention to ever get…
theHobbyist
- 421
- 4
- 3
42
votes
3 answers
A fixed-depth characterization of $TC^0$? $NC^1$?
This is a question about circuit complexity. (Definitions are at the bottom.)
Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{poly(\log s)}$ of depth two, where the output gate…
Ryan Williams
- 27,465
- 7
- 115
- 164
41
votes
12 answers
Gröbner bases in TCS?
Does anyone know of interesting applications of Gröbner bases to theoretical computer science?
Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was wondering whether some tractable special cases…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
41
votes
2 answers
Sum-of-square-roots-hard problems?
The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater than the sum $\sum_i \sqrt{b_i}$. The complexity…
Jeffε
- 23,129
- 10
- 96
- 163
41
votes
4 answers
Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?
I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:
It uses O(1) space
It can be updated to reflect an insertion or deletion in O(1) time
Two identical collections (i.e.,…
jonderry
- 747
- 1
- 5
- 8
41
votes
4 answers
Is $PH \subseteq PP$?
We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$.
Do we know whether $PH \subseteq PP$? If not, why is it that $P$ with…
Huck Bennett
- 4,868
- 2
- 33
- 46
41
votes
7 answers
When does randomization speed up algorithms and it "shouldn't"?
Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic algorithm for the problem that runs in time…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
41
votes
1 answer
Does Rabin/Yao exist (at least in a form that can be cited)?
In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation". This is for the result that the bounded-error communication complexity of the equality function EQ$_N$ (whether two integers in the range $0$ to…
András Salamon
- 19,000
- 3
- 64
- 150
41
votes
6 answers
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and analyse algorithms.
As a result, we have dozen of…
Tatiana Starikovskaya
- 821
- 6
- 9
41
votes
5 answers
What is the smallest Turing machine where it is unknown if it halts or not?
I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest one where nobody has a proof whether it halts or…
Aaron
- 547
- 4
- 9
41
votes
8 answers
Why go to theoretical computer science/research?
I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I wanted to work with AI, probably game dev.], but now I…
JulioC
- 171
- 1
- 3
- 7