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 | |
Results tagged with open-problem
Search options answers only
not deleted
user 495
Problems known to be open in the literature and any problem that, after being posed, is decided to be open by the community.
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.
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 …
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 …
- 21.1k
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.
- 21.1k
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 …
- 21.1k
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.
- 21.1k