Search Results
Search type | Search syntax |
---|---|
Tags | [tag] |
Exact | "words here" |
Author |
user:1234 user:me (yours) |
Score |
score:3 (3+) score:0 (none) |
Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
Views | views:250 |
Code | code:"if (foo != bar)" |
Sections |
title:apples body:"apples oranges" |
URL | url:"*.example.com" |
Saves | in:saves |
Status |
closed:yes duplicate:no migrated:no wiki:no |
Types |
is:question is:answer |
Exclude |
-[tag] -apples |
For more details on advanced search visit our help page |
Problems known to be open in the literature and any problem that, after being posed, is decided to be open by the community.
4
votes
"Refined" list of open problems in TCS
There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.
12
votes
How hard is unshuffling a string?
Romeo Rizzi and Stéphane Vialette prove that recognizing square strings is NP-complete in their 2013 paper "On Recognizing Words That Are Squares for the Shuffle Product", by reduction from the longes …
3
votes
Positive topological ordering, take 3
This paper, Obtaining a triangular matrix by independent row-column permutations Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.
11
votes
Problems between NC and P: How many have been resolved from this list?
The parallel complexity of the graph closure problem (problem $B.1.4$, posed by Khuller) was resolved By Angelo Monti. He showed that the graph closure problem is P-complete.
Angelo Monti, On the com …
15
votes
Major unsolved problems in theoretical computer science?
Proving the existence of hard-on-average problems in NP using the P≠NP assumption.
Bogdanov and Trevisan, Average-Case Complexity, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 …
8
votes
Major unsolved problems in theoretical computer science?
Algebraic dichotomy conjecture (Bulatov, Jeavons and Krokhin): Assuming ETH, every constraint satisfaction problem is either in $P$ or requires $2^{
\Omega(n)}$ time.