Most Popular
1500 questions
32
votes
2 answers
How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?
In this guest post by Josh Grochow at the complexity weblog he reports on a recent workshop devoted to GCT that was held at Princeton in July.
Several of the attendees argued that we should use GCT to attack easier problems than $\mathsf{P}$ vs.…
Mugizi Rwebangira
- 1,278
- 10
- 18
32
votes
5 answers
"Directed" problems that are easier than their "undirected" variant.
I was presenting a lecture on pancake sorting, and mentioned that:
Sorting by reversals is NP-hard
"signed" sorting by reversals is in P.
Which got me thinking. There is a sense in which "signed" sorting is "directed" - you can view the sign as…
Suresh Venkat
- 32,071
- 4
- 95
- 271
32
votes
5 answers
Efficiently computable variants of Kolmogorov complexity
Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:
It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
32
votes
5 answers
Counting words accepted by a regular grammar
Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of interest.
Margareta Ackerman has two papers on the…
Charles
- 1,735
- 12
- 23
32
votes
2 answers
Derandomizing Valiant-Vazirani?
The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an unsatisfiable formula - then NP=RP. This theorem…
Henry Yuen
- 3,798
- 1
- 21
- 33
32
votes
4 answers
Relationship between contracts and dependent typing
I've been reading some articles on dependent types and programming contracts. From the majority of what I've read, it seems that contracts are dynamically checked constraints and dependent types are statically checked.
There have been some papers…
Brian McKenna
- 422
- 3
- 7
32
votes
11 answers
What is the quantum computational model?
I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the computational model behind this. To be clear, I am not…
Casebash
- 475
- 3
- 8
32
votes
2 answers
NP-intermediate problems with efficient quantum solutions
Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) only yields a quadratic improvement over the…
Huck Bennett
- 4,868
- 2
- 33
- 46
32
votes
2 answers
Quantum matrix multiplication?
It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model? Do we have any intuition that we can beat the complexity of the Coppersmith-Winograd…
Henry Yuen
- 3,798
- 1
- 21
- 33
32
votes
13 answers
Are there any counterintuitive results in theoretical computer science?
Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?
By paradoxes I mean counter intuitive results that look like a contradiction.
serg
- 129
- 2
- 5
32
votes
3 answers
Is this variation of TQBF still PSPACE-complete?
Deciding if a quantified boolean formula such as
$\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$
always evaluates to true is a classical PSPACE-complete problem. This can be viewed as a game between two…
JWM
- 742
- 4
- 9
32
votes
4 answers
Can a probabilistic Turing machine solve the halting problem?
A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem?
That is, can a probabilistic computer determine whether or not a…
Joey Adams
- 437
- 4
- 4
32
votes
5 answers
Maximal classes for which largest independent set can be found in polynomial time?
The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile a list of maximal IS-easy classes. These classes…
András Salamon
- 19,000
- 3
- 64
- 150
32
votes
4 answers
What is simplest polynomial algorithm for PLANARITY?
There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm that one could easily and fast explain in class and…
domotorp
- 13,931
- 37
- 93
32
votes
4 answers
Hardness of approximation assuming NP != coNP
Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am looking for problem $A$ such that "it is hard to…
Shiva Kintali
- 10,578
- 41
- 74