Skip to main content
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
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.

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.
Mohammad Al-Turkistany's user avatar
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 …
Mohammad Al-Turkistany's user avatar
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.
Mohammad Al-Turkistany's user avatar
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 …
András Salamon's user avatar
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 …
Mohammad Al-Turkistany's user avatar
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.
Mohammad Al-Turkistany's user avatar