Most Popular
1500 questions
28
votes
1 answer
Are there subexponential algorithms for PLANAR SAT known?
Some NP-hard problems which are exponential on general
graphs are subexponential on planar graphs because the
treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential
in the treewidth.
Basically I am interested if there are…
joro
- 1,955
- 1
- 12
- 22
28
votes
2 answers
A category of NP-complete problems?
Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, where can I find it?
Paul Allen Grubbs
- 381
- 2
- 3
28
votes
3 answers
Impact of Grothendieck's program on TCS
Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's Contributions to Computer Science.
What are…
vzn
- 11,014
- 2
- 31
- 64
28
votes
6 answers
Natural NP-complete problems with "large" witnesses
The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but
Are there natural NP-complete problems in which (yes) instances
of size $n$ require witnesses of…
Marzio De Biasi
- 22,915
- 2
- 58
- 127
28
votes
2 answers
Kolmogorov's conjecture that $P$ has linear-size circuits
In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find anything online. Does anyone know more about…
Hamid
- 381
- 2
- 4
28
votes
2 answers
Bounded-input bijections of infinite sequences
Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution.
It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ using the properties of bicartesian closed…
Colin McQuillan
- 3,546
- 22
- 29
28
votes
2 answers
Reasons to believe $P \ne NP \cap coNP$ (or not)
It seems that many people believe that $P \ne NP \cap coNP$, in part because they believe that factoring is not polytime solvable. (Shiva Kintali has listed a few other candidate problems here).
On the other hand, Grötschel, Lovász, and Schrijver…
Austin Buchanan
- 1,166
- 1
- 17
- 28
28
votes
12 answers
What are the popular science books that inspire TCS?
There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true!
(In the same spirit of list of What Books Should Everyone Read?, What papers should everyone read?, What videos should…
Subhayan
- 831
- 9
- 19
28
votes
1 answer
Is uniform RNC contained in polylog space?
Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL). Is log-space-uniform RNC also in this class? The standard randomized version of PolyL should be in PolyL, but I don't see that (uniform) RNC is in…
Ryan O'Donnell
- 1,811
- 17
- 21
28
votes
6 answers
Alternative proofs of Schwartz–Zippel lemma
I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.
Are there any other proofs which use substantially different ideas?
Dai Le
- 3,664
- 1
- 24
- 37
28
votes
2 answers
Hamiltonicity of k-regular graphs
It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to…
David Eppstein
- 50,990
- 3
- 170
- 278
28
votes
6 answers
How should I think about proof nets?
In his answer to this question, Stephane Gimenez pointed me to a polynomial-time normalization algorithm for proofs in linear logic. The proof in Girard's paper uses proof nets, which are an aspect of linear logic I don't actually know very much…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
28
votes
4 answers
Church's Theorem and Gödel's Incompleteness Theorems
I have recently been reading up on some of the ideas and history of the ground-breaking work done by various logicians and mathematicians regarding computability. While the individual concepts are fairly clear to me, I'm am trying to get a firm…
Noldorin
- 857
- 1
- 9
- 12
28
votes
5 answers
To what extent is "advanced mathematics" needed/useful in A.I. research?
I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in artificial intelligence. However, I am not sure how many…
Max Muller
- 647
- 1
- 6
- 9
28
votes
2 answers
Approximate counting problem capturing BQP
In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say).
Is there a similar problem for BQP? This comment by…
Manu
- 7,659
- 3
- 37
- 42