Most Popular
1500 questions
38
votes
3 answers
Complexity of exponential function
We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.
Is this the main reason for the difficulty of…
Peter
- 381
- 3
- 4
38
votes
3 answers
Why does randomness have stronger effect on reductions than on algorithms?
It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite different effect on polynomial time reductions. By…
Andras Farago
- 11,396
- 37
- 70
37
votes
1 answer
What's the relation and difference between Calculus of Inductive Constructions and Intuitionistic Type Theory?
As stated in the title, I wonder any relation and difference between CIC and ITT. Could someone explain or point to me some literature that compares these two systems? Thanks.
day
- 2,795
- 1
- 20
- 27
37
votes
6 answers
Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?
A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover).
Does anyone know of a problem which is polytime solvable for $R^1$ and $R^2$, but…
Bob Fraser
- 534
- 3
- 9
37
votes
1 answer
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.
Conjecture. Let $\mu(k)$ be the Möbius function. Suppose $f: \mathbb{N} \to…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83
37
votes
5 answers
NEXP-complete problems
There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one available? As I assume there isn't, I open this…
slimton
- 1,570
- 14
- 18
37
votes
8 answers
Problems with big open complexity gaps
This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves.
To be more precise, let's say a problem has gap classes $A,B$…
Denis
- 8,843
- 28
- 55
37
votes
2 answers
If P=NP, could we obtain proofs of Goldbach's Conjecture etc.?
This is a naive question, out of my expertise; apologies in advance.
Goldbach's Conjecture and many other unsolved questions in mathematics can be written
as short formulas in predicate calculus.
For example, Cook's paper "Can Computers Routinely…
Joseph O'Rourke
- 3,753
- 23
- 41
37
votes
9 answers
Surprising Results in Complexity (Not on the Complexity Blog List)
What were the most surprising results in complexity?
I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of nowhere and also results that turned out different than…
Lev Reyzin
- 11,968
- 13
- 63
- 103
37
votes
5 answers
Integer multiplication when one integer is fixed
$n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of multiplication function $f_n(x)=a_nx$ where…
Turbo
- 12,812
- 1
- 19
- 68
37
votes
5 answers
When should you say what you know?
What should you do when you see a question raised in public, say here on stack-exchange, that you know the answer to, because you are looking into as part of current research project?
For example, I see a TCS.SX question that I know the answer to,…
asterix
- 331
- 2
- 4
37
votes
3 answers
Parameterized complexity of Hitting Set in finite VC-dimension
I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and a positive integer k, does X contain a subset of…
James King
- 2,613
- 18
- 25
37
votes
4 answers
Research and open challenges in Programming Language Theory
In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming languages. I hope that the discussion might even bring…
zpavlinovic
- 296
- 1
- 5
- 10
37
votes
2 answers
Origins and applications of Theory A vs Theory B?
In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of algorithms and complexity.
This terminology was new to…
Marc Hamann
- 2,904
- 1
- 24
- 22
37
votes
4 answers
Hardness of approximation without the PCP theorem
An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any case where the hardness of approximation result…
Andras Farago
- 11,396
- 37
- 70