All Questions
1,808 questions
26
votes
4
answers
6k
views
Discrete logs vs. factoring
One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...
- 12.6k
1
vote
4
answers
3k
views
A subset of all languages which is uncountable?
Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all ...
- 2,416
26
votes
6
answers
7k
views
Are there any interesting examples of random NP-complete problems?
Here's an example of the kind of thing I mean. Let's consider a random instance of 3-SAT, where you choose enough clauses for the formula to be almost certainly unsatisfiable, but not too many more ...
- 29k
5
votes
5
answers
1k
views
Quantum Computing Complexity?
After reading a recent post on Church's Thesis, I ran into Turing-Church's Strong Thesis, that may be potentially disproven by advances in Quantum Computing. Does anyone know of a good resource that ...
- 1,801
8
votes
1
answer
793
views
Pseudorandom generators
Has there been any progress about constructing strong pseudorandom generators?
I'm not an expert on this topic, basically everything I know is a definition of a pseudorandom generator, the idea that ...
3
votes
3
answers
5k
views
Determining the space complexity of van Emde Boas trees
We call $S(u)$ the space complexity of the vEB tree holding elements in the range $0$ to $u-1$, and suppose without loss of generality that $u$ is of the form $2^{2^k}$.
It's easy to get the ...
- 1,015
12
votes
5
answers
5k
views
Characterize P^NP (a.k.a. Delta_2^p)
What can you say about the complexity class $\text{P}^{\text{NP}}$, i.e. decision problems solvable by a polytime TM with an oracle for SAT? This class is also known as $\Delta_2^p$.
Obviously $\text{...
- 213
1
vote
3
answers
1k
views
How can one characterize NP^SAT?
Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
- 213