# Major unsolved problems in theoretical computer science?

Wikipedia only lists two problems under "unsolved problems in computer science":

What are other major problems that should be added to this list?

Rules:

1. Only one problem per answer
2. Provide a brief description and any relevant links
• Comments are not for extended discussion; this conversation has been moved to chat. Sep 20, 2022 at 18:47

Sensitivity versus block sensitivity

Boolean sensitivity is interesting because block sensitivity, a close relative, is polynomially related to several other important and interesting complexity measures (like the certificate complexity of a boolean function). If sensitivity is always related to block sensitivity in a polynomial way, we have an extremely simple characteristic of boolean function that's related to so many others.

One might read Rubinstein's "Sensitivity vs. block sensitivity of Boolean functions" or Kenyon and Kutin's "Sensitivity, block sensitivity, and l-block sensitivity of boolean functions."

• That's a great open problem, but I think that it can't be placed together with the fundamental open problems of the field (e.g., P vs NP) in the same league of "the major problems of TCS". Oct 21, 2010 at 20:22
• Now resolved! (should be removed?) Sep 15, 2019 at 18:03

Is BQP in PH (polynomial hierachy)?

Does there exist any hypothesis class that is NP-Hard to (improperly) PAC learn?

This has some possible implications for complexity, and I think the best progress on this question is here: http://www.cs.princeton.edu/~dxiao/docs/ABX08.pdf

Are NP-completeness in the sense of Cook and NP-completeness in the sense of Karp different concepts, assuming P $\neq$ NP?

The "P vs NP" question extends naturally to polynomial-time hierarchy (PH): "Whether PH has infinite levels, or it collapses to some finite level?"

I think this question is (or should be considered as) the most intriguing question of the computer science: If PH has infinite levels, then $\mathbf{P} \neq \mathbf{NP}$. In addition, several researchers have shown that if Graph Isomorphism is NP-complete, then PH collapses to the 2nd level. Therefore, if PH has infinite levels, then Graph Isomorphism is provably not NP-complete.

Several other results follow from the infiniteness of the levels of PH.

What about proving BPP is contained in NP? (Unconditionally; we already know that BPP=P assuming pretty reasonable complexity assumptions)

Is there an algorithm to compute the generalized star-height of a given regular language?

Generalized regular expressions are defined like regular expressions, but they allow the complement operator. The generalized star height (gsh) of a regular language is the minimum nesting depth of Kleene stars needed to represent the language by a generalized regular expression. Regular languages of gsh 0 (also known as star-free languages) have two nice characterizations: Schützenberger gave an algebraic characterization (their syntactic monoid is aperiodic) and McNaughton showed they correspond to FO[<].

It follows that there are languages of gsh $1$, like $(aa)^*$, but no language of gsh $> 1$ is known! Thus a subproblem would be first to find such a language, or to prove that all regular languages have gsh 1. See also http://www.liafa.univ-paris-diderot.fr/~jep/Problemes/starheight.html

• Welcome to cstheory.stackexchange! Very interesting that no language of gsh > 1 is known. Are there even candidate languages that people think might not have gsh = 1? Or a regular language whose gsh is unknown? Or is it that all regular languages that anyone has ever checked have gsh$\leq 1$? Aug 8, 2013 at 13:58
• @JoshuaGrochow It is likely that complicated examples can be found as follows: take a large permutation group, say $S_9$ generated by a cycle $a$ and a transposition $b$. Now consider the (regular) language of all words whose value in $S_9$ is the identity. One can hope that this language has gsh $> 1$. On the other hand, some people believe that every regular language has gsh $\leqslant 1$. Actually, one could define an "intermediate star-height" by replacing complement by intersection, but even so, I don't know of any language of intermediate star-height $> 1$. Aug 9, 2013 at 22:54

Another open problem for the lambda calculus (from TLCA list of open problems; PDF version ).

Problem #22 on the list:

Is there a continuously complete CPO model of the $\lambda$-calculus whose theory is precisely λβη or λβ ?

Is there a best algorithm for integer multiplication and matrix multiplication (MM), or for that matter any other familiar problem? Manuel Blum has suggested these are good candidates not to have a best algorithm. Among bilinear identities such as Strassen's there is no best one according to Coppersmith and Winograd (1982). If the conjectures of Umans et al are correct, then there is no best algorithm of the type they study. For relevant articles Google "Speedup for Natural Problems".

• Can you be more specific on you mean by a "best algorithm"? (There is a general linear speed-up theorem.) Nov 16, 2010 at 4:31

The word "major" is a bit frightening and takes us to the P/NP and related questions. Among the almost-major problems which might be feasible, one that I like is the question of randomized decision trees for graph properties. Is it true that for every non-trivial monotone graph property for graphs with n vertices the expected number of queries that you need to ask in order to know if the graph satisfy the property is constant n^2.

This conjecture is known as the Aanderaa-Karp-Rosenberg conjecture.

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 (2006) 1–106

• Actually, proving the existence of hard-on-average problems in NP based on any reasonable assumption would be great. Jun 8, 2012 at 23:56
• Is this related to the existance of one-way functions? Feb 5, 2015 at 7:32

K-server conjecture and randomized K-server conjecture.

Definition according to wikipedia

An online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests.

Unconditional derandomization of Arthur-Merlin games. It is also known that under hardness assumptions AM = NP. The question is, can we prove unconditionally that AM is a subset of sigma sub 2: http://cs.haifa.ac.il/~ronen/online_papers/online_papers.html

• Could you link to one paper instead of a collection? Oct 27, 2017 at 3:38

### Open Problem Lists

• The number of answers spans over a page. I think a list of responses (similar to other big-list questions) would be useful. Oct 11, 2015 at 19:40

Open Problem Garden hosts a number of unsolved problems in theoretical computer science.

• Could you find examples of major open problems that we don't have on this list yet, and post them as separate answers? Sep 5, 2010 at 10:09
• Sure Jukka you got it. Sep 5, 2010 at 13:53

Proving that BPP is in NP is harder than separating NEXP from BPP

That BPP is in NP implies that the polynomial identity problem is in NP, which separates NEXP from P/Poly (BPP is in P/Poly).

• Indeed, proving "BPP is in NP" necessarily "separates BPP from NEXP", because NP and NEXP are separated. But BPP is contained in NP (or in NTIME(..somewhat more than poly..)) is a concrete inclusion I would really like to see proven in the near future. Oct 18, 2010 at 11:13

It seems strange to me that almost all the answers are about computational complexity, while the question asks for problems in all computer science.

To counter-balance a little bit:

Decidability of the dot-depth hierarchy: Given a first-order formula on finite words and an integer $k$, is there an equivalent first-order formula with only $k$ quantifier alternations?

Recent progress has been made, it has been showed decidable for $k=2$ in a 2014 paper by Thomas Place and Marc Zeitoun, but the general problem is still wide open.

Algebraic dichotomy conjecture (Bulatov, Jeavons and Krokhin): Assuming ETH, every constraint satisfaction problem is either in $P$ or requires $2^{ \Omega(n)}$ time.

• Note that the dichotomy only applies to CSPs of a particular form, those consisting of all instances expressible with a fixed set of constraint relations. Moreover, there is a further technical issue, whether every set of constraint relations that is NP-complete can be equivalently represented by a finite set of relations. Nov 13, 2010 at 20:46

The Open Problems Project: http://cs.smith.edu/~orourke/TOPP/

Is Quasi-Polynomial Time in PSPACE?

Can we multiply two arbitrary $$n$$-bit numbers in $$O(n)$$ time? There is a trivial lower bound of $$\Omega(n)$$, but no better lower bound is known. Currently, the asymptotically fastest algorithm is $$O(n \log n)$$ - a recent breakthrough by Harvey and van der Hoeven 2019. The previous best took time $$O(n \log n 2^{\log^* n})$$ due to Martin Fürer, building off of the original algorithm by Schönhage–Strassen which ran in $$\Theta(n \log n \log \log n)$$ time. Regan and Lipton showed that a super-linear lower bound would follow from the Hartmanis-Stearns Real-Time Computability Conjecture.

A recent result of Afshani, Freksen, Kamma, and Larsen established the following conditional lower bound: assuming the network coding conjecture, any constant-degree Boolean circuit for multiplication must have size $$\Omega(n\log n)$$.

• This is a clearer exposition than an earlier version of the question by J.A from 2012. Mar 3, 2014 at 15:03
• Maybe "asymptotically fastest" was a typo when referring to Schonhage-Strassen (since you then cite Furer's algorithm which is asymptotically faster...)? Sep 18, 2014 at 19:52
• Wouldn't it be good to mention the recent (conditional) lower bound based on the network coding conjecture? @JoshuaGrochow Sep 15, 2019 at 19:34
• @ClementC. Is network coding complexity theoretic? Sep 16, 2019 at 2:09
• @T.... The lower bound is. "Assuming [conjecture], any constant degree boolean circuit for multiplication must have size $\Omega(n\log n)$." Sep 16, 2019 at 2:11
• Do a pseudo-randomized numbers generator exist?
• If one way function exists, then PRG exist. That is a very well known results from late 80s. So this doesn't make it a independent unresolved problem because if you start counting this, then so does most of the cryptographic primitives that can be constructed by OWF. Jan 27, 2012 at 5:12

If P != NP, Does the polynomial hierarchy collapse?

(Because if P = NP then it completely collapses, of course)

Finding natural SampNP-complete distributional problems.

Informally, Samp-NP is the class of NP problems restricted to distributions that are samplable in polynomial time ("On the Theory of Average Case Complexity", Ben-David, Chor, Goldreich and Luby, JCSS 1992, doi:10.1016/0022-0000(92)90019-F). This class aims to capture the complexity of solving NP on real life instances. While it is known that this class has complete problems, we do not know of any natural complete problems for this class. Finding such a problem would yield the first natural problem for which we have good theoretical reasons to believe that it is hard on average.

Some open problems in complexity theory lower bounds, together with their relationships, are mapped here.

• nice, useful, detailed, how about more of a summary/abstract on the misc relationships covered (which isnt really in the abstract either)
– vzn
Mar 3, 2014 at 1:07

Getting an O(1) factor approximation algorithm in polytime for the Maximum Independent Set of Rectangles.

This is one of the biggest open problems in Computational Geometry. Recently, Anna Adamaszek and Andreas Wiese  have given a QPTAS for this problem, which shows the existence of a PTAS assuming standard complexity theory conjectures. However even a constant factor approximation is not known yet that can be achieved in polytime. The best known polytime approximation factor is $O(\log \log n)$ . More recently, Abed et al.  have given a constant factor approximation based on a conjecture.

Is $\mathsf{L}=\mathsf{NL}$? What about non-uniform versions?

• Links or references, please. When you edit, would you consider make it standard fonts like everybody else? Jun 8, 2012 at 12:09
• Please use regular fonts. and run a spell checker Jun 9, 2012 at 0:12

Conjunctive query containment over bag semantics

In a GoogleFight between two search queries, can one tell if the first query always wins, without looking at the data?

This 1993 question from database theory  asks whether it is possible to decide if an SQL query (more precisely, a conjunctive query) always yields at least as many answers as another conjunctive query, over all possible databases. It would be nice to answer this question to help with query optimization.

One can also formalise the question without referring to databases (see also ):

Homomorphism Domination
Input: finite relational structures $S$ and $S'$.
Question: is it true that for any finite relational structure $T$, there are at least as many relational structure homomorphisms from $S$ to $T$ as there are from $S'$ to $T$?

Since the quantification is over an infinite set of structures $T$, this may be undecidable. It is known to be NP-hard  as a special case of a more general question over positive semirings (the non-negative integers with addition and multiplication is a semiring); $\Pi^P_2$-hardness was claimed two decades ago but remains unclear. If instead of conjunctive queries, slightly more general queries are allowed, then the problem does become undecidable, via reductions from Hilbert's 10th problem [4,5].

What makes this question interesting is that for most positive semirings of interest the general question is decidable, and actually in $\Pi_2^P$. In fact, for the Boolean semiring case the question becomes: given two conjunctive queries, is it always true that when the first query has an answer then so does the second? Ashok Chandra and Philip Merlin showed in 1977  that this is equivalent to checking whether there exists a homomorphism between the queries, which is in NP. Moreover, in typical databases the queries are usually small or even fixed, while the data is large and changes frequently. This means that even brute force search for a homomorphism between the input queries may be worthwhile.

So it might be a good idea to look quite closely at two small fixed conjunctive queries to decide which is the better one to use. Yet we don't know if such queries can be compared based on the number of answers they generate.

Edit: added some key references as requested by Sylvain.

1. Surajit Chaudhuri and Moshe Y. Vardi, Optimization of Real Conjunctive Queries, PODS 1993, 59–70. doi:10.1145/153850.153856
2. Swastik Kopparty and Benjamin Rossman, The homomorphism domination exponent, EJOC 2011, 32(7) 1097–1114. doi:10.1016/j.ejc.2011.03.009
3. Egor V. Kostylev, Juan L. Reutter, and András Z. Salamon, Classification of Annotation Semirings over Containment of Conjunctive Queries, TODS 2014, 39(1) 1:1–39. doi:10.1145/2556524
4. Yannis E. Ioannidis and Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, TODS 1995, 20(3) 288–324. doi:10.1145/211414.211419
5. T.S. Jayram, Phokion G. Kolaitis, and Erik Vee, The containment problem for Real conjunctive queries with inequalities, PODS 2006, 80–89. doi:10.1145/1142351.1142363
6. Ashok K. Chandra and Philip M. Merlin, Optimal Implementation of Conjunctive Queries in Relational Data Bases, STOC 1977, 77–90. doi:10.1145/800105.803397
• Nice one. Could you provide more links to the literature, on decidable cases etc. ? Feb 28, 2014 at 21:44
• @Sylvain: as is usual here, I have avoided linking directly to my own work but our TODS 2014 paper has all the key links. Feb 28, 2014 at 23:36
• Since I'm not bound by such usage habits, here is a link for others who might be interested: tods.acm.org/accepted/2013/SalamonClassification.pdf. You could however provide a link to the PODS 1993 Chaudhuri & Vardi paper at dx.doi.org/10.1145/153850.153856 without being suspected of self-promotion. Mar 1, 2014 at 15:52

In general, what is the relationship between time and space complexity classes?

There are many unresolved questions such as:

• Is $$PTIME = NLOGSPACE$$?

• Is $$PTIME = DLOGSPACE$$?

• Is $$PTIME = PSPACE$$?

• Is $$DSPACE(s(n)) \subseteq PTIME$$ for some $$s(n) = \omega(\log n)$$?

• Is $$DTIME(t(n)) \subseteq PSPACE$$ for some super polynomial function $$t(n)$$?

Also, there are several more specific questions coming out of classic research papers that were never fully answered:

• Is $$NSPACE(k \log(n)) \subseteq DTIME(n^{k - \varepsilon})$$ for any $$k$$ and $$\varepsilon > 0$$? (see conjecture from Kasai and Iwata 1985)

• Is $$DTIME(n) \subseteq DTISP(poly(n), \frac{n}{\log n})$$? (simulation from Hopcroft, Paul, Valiant 1977 only seems to work with super polynomial time complexity)

• Is $$NSPACE(\log(n)) \subseteq DTISP(poly(n), \log^2 n)$$? (simulation from Savitch's theorem only seems to work with super polynomial time complexity)

• Note: Even $NPTIME$ has not been shown to be different from $DLOGSPACE$. Feb 10, 2020 at 10:39
• There also are related questions involving $CFL$ and $DCFL$ along with time and space complexity classes. Feb 10, 2020 at 10:45

Can inductive-recursive types be constructed in univalent models of type theory?

Recently, Hugunin (2019) showed that inductive-inductive types are compatible with univalent models of type theory, and demonstrated how to construct them in cubical type theory. The case for inductive-recursive types, by far, is still unclear.

Some more open problems in type theory here.