<blockquote>
<p>Can multiplication of <span class="math-container">$n$</span> by <span class="math-container">$n$</span> matrices be done in <span class="math-container">$O(n^2)$</span> operations?</p>
</blockquote>
<p>The exponent of the best known upper bound even has a special symbol, <span class="math-container">$\omega$</span>. Currently <span class="math-container">$\omega$</span> is approximately 2.376, by the <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="noreferrer">Coppersmith-Winograd algorithm</a>.  A nice overview <strike>of the state of the art</strike> is Sara Robinson, <a href="http://www.siam.org/news/news.php?id=174" rel="noreferrer"><em>Toward an Optimal Algorithm for Matrix Multiplication</em></a>, SIAM News, 38(9), 2005.</p>
<p><strong>Update</strong>: Andrew Stothers (in his 2010 <a href="http://hdl.handle.net/1842/4734" rel="noreferrer">thesis</a>) showed that <span class="math-container">$\omega &lt; 2.3737$</span>, which was improved by Virginia Vassilevska Williams (in a July 2014 <a href="http://www.cs.berkeley.edu/%7Evirgi/matrixmult-f.pdf" rel="noreferrer">preprint</a>) to <span class="math-container">$\omega &lt; 2.372873$</span>.  These bounds were both obtained by a careful analysis of the basic Coppersmith-Winograd technique.</p>
<p><strong>Update</strong> (Jan 30, 2014): François Le Gall has proved that <span class="math-container">$\omega &lt; 2.3728639$</span> in a paper published in ISSAC 2014 (<a href="http://arxiv.org/abs/1401.7714v1" rel="noreferrer">arXiv preprint</a>).</p>
<p><strong>Update</strong> (Nov 4, 2023): &quot;<a href="https://arxiv.org/abs/2307.07970" rel="noreferrer">New Bounds for Matrix Multiplication: from Alpha to Omega</a>&quot; proved that <span class="math-container">$\omega \leq 2.371552$</span>.</p>

CC BY-SA 3.0
2011-12-08T22:27:57.147Z
Just adding for the sake of completeness wrt current knowledge that CW bound was bettered a few days ago by Virginia Williams. And as noted by many others in the community, Andrew Stothers had obtained his bound beating CW's around one year before Virginia. The current record is $O(n^{2.373})$
Akash Kumar
CC BY-SA 3.0
2012-02-02T09:51:11.947Z
I will just let this here http://research.microsoft.com/en-us/um/people/kannan/papers/matrixmult.pdf
raven
CC BY-SA 3.0
2012-02-03T11:53:59.167Z
@JaimePardos: the full version of the approximate matrix multiplication paper you refer to is http://www.stanford.edu/class/ee378B/papers/drineas-kannan-mahoney-monte-carlo1.pdf which focuses on algorithms with few passes over the data, with a more generally useful analysis of running time.  TL;DR: matrix multiplication can be approximated for some kinds of matrices in $O(n^2)$ time.
András Salamon
CC BY-SA 3.0
2014-01-31T17:35:38.357Z
Even more embarrassing that we don't know the optimal algorithms for smallish matrices. NSF/DARPA should really fund cranking these out on spare supercomputing cycles so the chip makers can start cranking out optimal 64 x 64 MATMUL accelerators. Also a low power 8x8 unit would be a killer application for Micron's new venture to sprinkle compute blocks around RAM.
Chad Brewbaker
CC BY-SA 3.0
2016-09-22T16:37:45.930Z
@AndrásSalamon I think it is known time complexity has to be $\omega(n^2)$ since circuit complexity is at least this much (http://dl.acm.org/citation.cfm?id=509932 result by Raz).
Turbo
CC BY-SA 2.5
2010-09-13T17:16:42.883Z
How about a modest and realistic goal of $O(n^2 \log n)$ or some other function between $n^{2+\epsilon}$ and $n^2$? After all it is expected that integer multiplication has the lower bound of $O(n \log n)$.
Mitch
CC BY-SA 2.5
2010-09-13T17:39:21.187Z
I'm not sure going from even $2+0.376$ to $2+\epsilon$ is regarded as a "modest and realistic goal", let alone then going below $2+\epsilon$.  But it would be great to see some progress, so give it a shot!
András Salamon
CC BY-SA 2.5
2010-11-13T02:39:25.757Z
The matrix multiplication exponent is defined to be the smallest real number $\omega$ such that $O(n^{\omega+\epsilon})$ arithmetic operations suffice for all $\epsilon>0$. Probably a factor like $\log n$ should be expected.
Zeyu
CC BY-SA 4.0
2010-08-17T17:43:26.000Z
2023-11-14T09:31:13.563Z
2023-11-14T09:31:13.563Z
András Salamon
<blockquote>
  <p>Is Graph Isomorphism in P?</p>
</blockquote>

<p>The complexity of Graph Isomorphism (GI) has been an open question for several decades.  Stephen Cook mentioned it in his <a href="http://4mhz.de/cook.html" rel="noreferrer">1971 paper on NP-completeness of SAT</a>.</p>

<p>Determining whether two graphs are isomorphic can usually be done quickly, for instance by software such as <a href="http://cs.anu.edu.au/~bdm/nauty/" rel="noreferrer"><code>nauty</code></a> and <a href="http://vlsicad.eecs.umich.edu/BK/SAUCY/" rel="noreferrer"><code>saucy</code></a>.  On the other hand, Miyazaki constructed <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.7911&amp;rep=rep1&amp;type=pdf" rel="noreferrer">classes of instances</a> for which <code>nauty</code> provably requires exponential time.</p>

<p>Read and Corneil reviewed the many attempts to tackle the complexity of GI up to that point: <a href="http://dx.doi.org/10.1002/jgt.3190010410" rel="noreferrer"><em>The Graph Isomorphism Disease</em></a>, Journal of Graph Theory <strong>1</strong>, 339–363, 1977.</p>

<p>GI is not known to be in co-NP, but there is a simple randomized protocol for Graph Non-Isomorphism (GNI).  So GI (= co-GNI) is therefore believed to be "close to" NP <span class="math-container">${}\cap{}$</span> co-NP.</p>

<p>On the other hand, if GI is NP-complete, then the Polynomial Hierarchy collapses.  So GI is unlikely to be NP-complete.  (Boppana, Håstad, Zachos, <a href="http://dx.doi.org/10.1016/0020-0190(87)90232-8" rel="noreferrer"><em>Does co-NP Have Short Interactive Proofs?</em></a>, IPL <strong>25</strong>, 127–132, 1987)</p>

<p>Shiva Kintali has a <a href="http://kintali.wordpress.com/2010/09/02/hardness-of-graph-isomorphism/" rel="noreferrer">nice discussion</a> of the complexity of GI at his blog.</p>

<p>Laszlo Babai proved that <a href="http://arxiv.org/abs/1512.03547" rel="noreferrer">Graph Isomorphism is in quasipolynomial time</a>.</p>

CC BY-SA 3.0
2014-01-31T17:25:11.430Z
I cranked an exact lower bound for generic brute force automorphism detection. http://oeis.org/A186202 Much less than $n!$ but still exponential.  Hoping McKay will couple it to the Schrier-Sims for his latest incarnation of NAUTY to make it run on parallel hardware.
Chad Brewbaker
CC BY-SA 3.0
2017-01-04T21:56:01.650Z
[Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.
Raphael
CC BY-SA 3.0
2017-07-07T17:34:06.197Z
The claim was restored : http://people.cs.uchicago.edu/~laci/update.html
niting
CC BY-SA 2.5
2010-09-07T20:59:04.710Z
Please take a look at [this entry](http://cstheory.stackexchange.com/questions/1064/polynomial-time-algorithm-for-graph-isomorphism-testing) as well.
Sadeq Dousti
CC BY-SA 4.0
2010-08-17T22:03:03.540Z
2020-01-22T21:32:18.027Z
2020-01-22T21:32:18.027Z
Kaveh
<h2>Complexity of Factoring</h2>
<p>Is <a href="http://en.wikipedia.org/wiki/Integer_factorization" rel="noreferrer">Factoring</a> in <span class="math-container">$\mathsf{P}$</span>?</p>
<ul>
<li><a href="https://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p">Consequences of Factoring being in P?</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard">Are the problems PRIMES, FACTORING known to be P-hard?</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete">What are the consequences of factoring being NP-complete?</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/4765/p-with-integer-factorization-oracle">P with integer factorization oracle</a></li>
<li><a href="https://mathoverflow.net/questions/79366/evidence-for-integer-factorization-is-in-p">Evidence for integer factorization is in P</a> (on <a href="https://mathoverflow.net/">MO</a>)</li>
</ul>

CC BY-SA 3.0
2014-01-31T17:45:16.560Z
Any good publications you know of that describe factoring or primality testing complexity in terms of the structure of the semigroup of addition and multiplication transforms on Z_n?  For example on $Z_3$  [0,1,2] is the +0|x1 transform, [1,2,0] is the +1 transform ...
Chad Brewbaker
CC BY-SA 3.0
2010-08-17T22:02:00.670Z
2012-01-28T23:08:48.817Z
2020-06-17T09:38:08.363Z
Kaveh
<p>The problem of whether <a href="https://en.m.wikipedia.org/wiki/P_%3D_BPP_problem" rel="nofollow noreferrer">P equals BPP</a>.</p>

CC BY-SA 2.5
2010-08-19T01:54:55.203Z
See the closely related question http://cstheory.stackexchange.com/questions/64/what-specific-evidence-is-there-for-p-rp
András Salamon
CC BY-SA 2.5
2010-08-17T17:38:33.683Z
This answer should be made CW now too...
Shane
CC BY-SA 2.5
2010-08-18T05:08:12.873Z
and related questions like is NP = MA = AM?
Robin Kothari
CC BY-SA 4.0
2010-08-17T17:17:51.360Z
2024-06-23T04:13:20.913Z
2024-06-23T04:13:20.913Z
didest
<p>Is there a pivoting rule for the simplex algorithm that yields worst-case polynomial running time?  More generally, is there any strongly polynomial algorithm for linear programming?</p>

CC BY-SA 3.0
2011-11-10T04:27:44.170Z
,,,and the Hirsch conjecture...
Sariel Har-Peled
CC BY-SA 3.0
2012-01-30T16:11:10.027Z
In 2011, Oliver Friedmann showed exponential lower bounds for many pivoting rules (he actually claims "essentially all natural" pivoting rules, including Random Facet and Random Edge).  These bounds apply when solving a linear program derived from 2-player parity games.  Friedmann's thesis http://edoc.ub.uni-muenchen.de/13294/ surveys the history in some depth (including various forms of the Hirsch Conjecture, and the 2010 counterexample to the strong form by Francisco Santos).
András Salamon
CC BY-SA 2.5
2010-08-27T23:59:22.560Z
I'll add to this question: would showing the nonexistence of strongly polynomial LP imply any class separation results?
Anand Kulkarni
CC BY-SA 2.5
2010-08-24T06:13:44.307Z
2010-08-30T19:47:56.753Z
2010-08-30T19:47:56.753Z
Jeffε
<p>The <strong>exponential-time hypothesis (ETH)</strong> asserts that solving SAT requires exponential, 2<sup>Ω(n)</sup> time.  ETH implies many things, for instance that SAT is not in P, so ETH implies P ≠ NP.  See Impagliazzo, Paturi, Zane, <a href="http://dx.doi.org/10.1006/jcss.2001.1774"><em>Which Problems Have Strongly Exponential Complexity?</em></a>, JCSS 63, 512–530, 2001.</p>

<p>ETH is widely believed, but likely to be difficult to prove, as it implies many other complexity class separations.</p>

CC BY-SA 2.5
2010-08-23T09:16:20.900Z
Seriously, I wouldn't call the ETH a major open problem at this point in time exactly because it implies P≠NP and thus is at least as difficult to prove.
Holger
CC BY-SA 2.5
2010-08-24T06:05:33.677Z
No?  IMHO, your argument implies that ETH is even more of a major open problem than PvsNP.
Jeffε
CC BY-SA 2.5
2010-08-31T12:23:40.080Z
Could you explain why $P \ne NP$ does not imply the ETH?
Emil
CC BY-SA 2.5
2010-08-31T15:30:04.847Z
If $NP = PTIME(n^{\log n})$, then $P\ne NP$, but ETH is false.
Jeffε
CC BY-SA 2.5
2010-09-01T14:03:20.347Z
Ah ok. But you mean DTIME($n^{\log n}$)?
Emil
CC BY-SA 2.5
2010-08-17T20:51:29.843Z
2010-08-18T00:13:02.773Z
2010-08-18T00:13:02.773Z
Jeffε
<p>Immerman and Vardi show that fixed-point logic captures PTIME on the class of <em>ordered</em> structures. One of the biggest open problems in descriptive complexity theory is whether the dependency on the order can be removed:</p>

<blockquote>
  <p>Is there a logic that captures PTIME?</p>
</blockquote>

<p>Put simply, a logic capturing PTIME is a programming language for graph problems that works directly on the graph structure and does not have access to the encoding of the vertices and edges, such that the following hold:</p>

<ol>
<li>any syntactically correct program models a polynomial-time computable graph problem and</li>
<li>any polynomial-time computable graph problem can be modelled by a syntactically correct program.</li>
</ol>

<p>If there is no logic that captures PTIME, then $P \neq NP$ since NP is captured by existential second-order logic. A logic capturing PTIME would provide a possible attack to P vs NP.</p>

<p>See <a href="http://rjlipton.wordpress.com/2010/04/05/graph-isomorphism-and-graph-minors/">Lipton's blog</a> for an informal discussion and <em>M. Grohe: <a href="http://www-i7.informatik.rwth-aachen.de/~grohe/pub/gro08b.pdf">The Quest for a Logic Capturing PTIME</a></em> (LICS 2008) for a more technical survey.</p>

CC BY-SA 2.5
2010-08-18T12:26:12.260Z
Immerman-Vardi shows FO(LFP) captures logic on <i>ordered</i> structures, so this is a question about capturing PTIME on arbitrary finite models, I take it.  If I understand you correctly, isn't this question a translation of asking whether P != NP?  It might be more pointed to ask one or more of the open problems in the survey you link to.  Apologies if I am being clueless here.
Aaron Sterling
CC BY-SA 2.5
2010-08-18T16:25:58.517Z
Thanks, I edited the answer to mention Immerman-Vardi for clarification. No, this open problem is not known to be equivalent to P vs NP. The open problems in the survey are special cases of the big open problem and not appropriate in this thread. Maybe this reference is also helpful: http://rjlipton.wordpress.com/2010/04/05/graph-isomorphism-and-graph-minors/
Holger
CC BY-SA 3.0
2010-08-18T09:55:45.397Z
2014-01-31T17:33:32.783Z
2014-01-31T17:33:32.783Z
Holger
<p><a href="http://en.wikipedia.org/wiki/Permanent">Permanent</a> versus <a href="http://en.wikipedia.org/wiki/Determinant">Determinant</a></p>

<p>The permanent versus determinant question is interesting because of two facts. First, the permanent of a matrix counts the number of perfect matchings in a bipartite graph. Therefore the permanent of such a matrix is #P-Complete. At the same time, the definition of the permanent is very close that of the determinant, ultimately different only because of a simple sign change. Determinant calculations are well known to be in P. Studying the different between the permanent and the determinant, and how many determinant calculations are required to compute the permanent speak about P versus #P.</p>

CC BY-SA 3.0
2011-12-09T00:59:02.450Z
To me this doesn't qualify as a "major open problem", because the actual complexity theoretic question (do they have different complexities) is subsumed by P=NP (since #P is a superset of NP) and with that question set aside there isn't a concrete problem posed here.
David Eppstein
CC BY-SA 3.0
2011-12-09T04:25:48.523Z
I actually agree with this.
Ross Snider
CC BY-SA 3.0
2012-03-02T17:38:38.707Z
@DavidEppstein: Per v. det is closer to GapP v GapL, a counting analog of NP v NL. It's possible that $NL \neq P=NP$ and hence $GapP \neq GapL$. Also, per v det is much older than P v NP, essentially going back to [Polya 1913], in which he shows that one cannot affix signs to a matrix to change its permanent to its determinant (except 2x2). Valiant introduced a variant on those questions (allowing size of det to be larger than n) because of its significance in complexity, but even the pre-Valiant works give the motivation "because the permanent is so hard to compute..." (eg Gibson 1971)
Joshua Grochow
CC BY-SA 3.0
2014-01-31T18:10:43.437Z
What are the state of the art algorithms now for calculating the permanent of a 0-1 matrix? i.e. the number of legal permutation matrices you can generate from a subset of the 1's.
Chad Brewbaker
CC BY-SA 3.0
2015-02-05T07:22:52.270Z
@ChadBrewbaker: see Mark Jerrum, Alistair Sinclair, Eric Vigoda, "A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Non-Negative Entries", *Journal of the ACM* 51/4 (2004), 671, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.116
Zsbán Ambrus
CC BY-SA 3.0
2010-08-17T20:12:00.407Z
2012-03-15T23:06:24.270Z
2012-03-15T23:06:24.270Z
Ross Snider
<p>Is the <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Unique_games_conjecture">unique games conjecture</a> true?<br>
And: Given that there are <a href="http://www.cs.princeton.edu/~dsteurer/subexpug.pdf">sub-exponential time approximation algorithms for Unique Games</a>, where does the problem ultimately rest in terms of the complexity landscape?</p>

CC BY-SA 3.0
2017-01-06T21:28:07.873Z
It's worth noting that there are no known hard instances of UCG. The current best approach works efficiently in every tested case. We just can't prove that we have found the most pathological examples.
Stella Biderman
CC BY-SA 2.5
2010-08-31T11:09:26.163Z
In retrospect, I thought I should include a pointer toward [this pre-print](http://eccc.hpi-web.de/report/2010/112/). In my opinion, it's as big of a development as the paper I have linked in the answer.
Daniel Apon
CC BY-SA 2.5
2010-08-17T17:55:45.647Z
Would it not be more precise to say that if the UGC is _not_ true (i.e. unique games are not NP-hard, just harder than P), where would UGC fit into the landscape?
András Salamon
CC BY-SA 2.5
2010-08-17T18:58:47.113Z
Oops. Yes, I should reword this. My intention was to highlight the the apparent discrepancy that results from unique games having a non-trivial approximation algorithm in sub-exponential (but not quite polynomial) time. More of: What does this say, if sub-exponential run time is optimal for unique games?
Daniel Apon
CC BY-SA 2.5
2010-08-17T17:49:50.870Z
2010-08-17T23:32:40.167Z
2010-08-17T23:32:40.167Z
Daniel Apon
<p>The <a href="http://en.wikipedia.org/wiki/Splay_tree#Dynamic_optimality_conjecture">dynamic optimality conjecture for splay trees.</a></p>

<p>Or more generally: Is <em>any</em> online dynamic binary search tree O(1)-competitive?</p>

CC BY-SA 2.5
2010-09-01T16:47:47.550Z
pretty much that's it.
Suresh Venkat
CC BY-SA 2.5
2010-10-16T14:03:24.537Z
There are also the more recent [zipper trees](http://arxiv.org/abs/1003.0139), which are O(lg lg n) competitive without giving up O(lg n) worst-case access time.
jbapple
CC BY-SA 2.5
2010-08-17T20:28:21.443Z
2010-08-17T20:28:21.443Z
Jeffε
<p>A linear time deterministic algorithm for the <a href="http://en.wikipedia.org/wiki/Minimum_spanning_tree">minimum spanning tree</a> problem. </p>

CC BY-SA 3.0
2010-08-18T05:07:59.127Z
2012-01-26T23:38:39.303Z
2012-01-26T23:38:39.303Z
Suresh Venkat
<p>Can we compute the <a href="http://en.wikipedia.org/wiki/Fft" rel="noreferrer">FFT</a> in much less than $O(n \log n)$ time?</p>

<p>In the same (very) general vein, there are many questions of improving the run-times of many classical problems or algorithms: e.g., can <a href="http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm" rel="noreferrer">all-pairs-shortest-paths (APSP)</a> be solved in $O(n^{3-\epsilon})$ time ?</p>

<p>Edit: APSP runs in time $(\frac{n^3}{2^{\Omega(log n)^{1/2}}})$ "where additions and
comparisons of reals are unit cost (but all other operations have typical logarithmic cost)": <a href="http://arxiv.org/pdf/1312.6680v2.pdf" rel="noreferrer">http://arxiv.org/pdf/1312.6680v2.pdf</a></p>

CC BY-SA 3.0
2012-02-02T16:20:08.067Z
An interesting development on FFT: "* An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and
* An O(k log n log(n/k))-time algorithm for general input signals." source: http://arxiv.org/abs/1201.2501v1
Shadok
CC BY-SA 3.0
2010-08-18T06:17:50.657Z
2014-11-03T02:21:52.027Z
2014-11-03T02:21:52.027Z
Alex Andoni
<p>NP versus co-NP</p>

<p>The NP versus co-NP question is interesting because NP ≠ co-NP implies P ≠ NP (as P is closed under complement).  It also relates to "duality": separation between finding/verifying examples and finding/verifying counterexamples. In fact, proving that a question is in both NP and co-NP is our first good evidence that a problem that seems to be outside of P is also likely not NP-Complete.</p>

CC BY-SA 2.5
2010-08-17T22:01:37.253Z
This is also related to propositional proof complexity. There is a polynomial propositional proof system iff $NP$ is equal to $coNP$.
Kaveh
CC BY-SA 2.5
2010-08-17T20:11:21.250Z
2010-08-18T00:03:36.320Z
2010-08-18T00:03:36.320Z
Ross Snider
<blockquote>
  <p>Do all propositional tautologies have polynomial-size Frege proofs?</p>
</blockquote>

<p><strong>Arguably the major open problem of proof complexity</strong>: demonstrate
super-polynomial size lower bounds on propositional proofs (called also Frege proofs). </p>

<p>Informally, a Frege proof system is just a standard propositional proof system for proving
propositional tautologies (one learns in a basic logic course), having axioms and deduction rules, where proof-lines are written as formulas. The <em>size</em> of
a Frege proof is the number of symbols it takes to write down the proof.</p>

<p>The problem then asks whether there is a family <span class="math-container">$(F_n)_{n=1}^\infty$</span> of propositional
tautological formulas for which there is no polynomial <span class="math-container">$ p $</span> such that the minimal Frege proof size of <span class="math-container">$ F_n $</span> is at most <span class="math-container">$ p(|F_n|)$</span>, for all <span class="math-container">$ n=1,2,\ldots$</span>  (where <span class="math-container">$ |F_n| $</span> denotes the size of the formula <span class="math-container">$ F_n $</span>).</p>

<hr>

<p><strong>Formal definition of a Frege proof system</strong></p>

<p><strong>Definition</strong> (Frege rule) A <em>Frege rule</em> is a sequence of propositional 
formulas <span class="math-container">$ A_0(\overline x),\ldots,A_k(\overline x) $</span>, for <span class="math-container">$ k \le 0 $</span>,
written as <span class="math-container">$ \frac{A_1(\overline x), \ldots,A_k(\overline
x)}{A_0(\overline x)}$</span>. In case <span class="math-container">$ k = 0 $</span>, the Frege rule is called
an <em>axiom scheme</em>. A formula <span class="math-container">$ F_0 $</span> is said to be <em>derived by the
rule</em> from <span class="math-container">$ F_1,\ldots,F_k $</span> if <span class="math-container">$ F_0,\ldots,F_k $</span> are all
substitution instances of <span class="math-container">$ A_1,\ldots,A_k $</span>, for some assignment to
the <span class="math-container">$ \overline x $</span> variables (that is, there are formulas
<span class="math-container">$B_1,\ldots,B_n $</span> such that <span class="math-container">$F_i = A_i(B_1/x_1,\ldots,B_n/x_n), $</span> for
all <span class="math-container">$ i=0,\ldots,k $</span>. The Frege rule is said to be <em>sound</em> if
whenever an assignment satisfies the formulas in the upper side
<span class="math-container">$A_1,\ldots,A_k $</span>, then it also satisfies the formula in the lower
side <span class="math-container">$ A_0 $</span>.</p>

<p><strong>Definition</strong> (Frege proof) 
Given a set of Frege rules, a <em>Frege proof</em> is a sequence of
formulas such that every proof-line is either an axiom or was derived
by one of the given Frege rules from previous proof-lines. If the
sequence terminates with the formula <span class="math-container">$ A $</span>, then the proof is said to
be <em>a proof of <span class="math-container">$ A $</span></em>. The <strong>size</strong> of a Frege proof is the the total sizes of 
all the formulas in the proof.</p>

<p>A proof system is said to be <em>implicationally complete</em> if for
all set of formulas <span class="math-container">$ T $</span>, if <span class="math-container">$ T $</span> semantically implies <span class="math-container">$ F $</span>, then
there is a proof of <span class="math-container">$ F $</span> using (possibly) axioms from <span class="math-container">$ T $</span>.
A proof system is said to be sound if it admits proofs of only
tautologies (when not using auxiliary axioms, like in the <span class="math-container">$ T $</span>
above).</p>

<p><strong>Definition</strong> (Frege proof system)
Given a propositional language and a finite set <span class="math-container">$ P $</span> of sound Frege rules,
 we say that <span class="math-container">$ P $</span> is <em>a Frege proof system</em> if <span class="math-container">$ P $</span> is
implicationally complete.</p>

<p>Note that a Frege proof is always sound since the Frege rules are
assumed to be sound. We do not need to work with a specific Frege proof system, since a
basic result in proof complexity states that every two Frege proof
systems, even over different languages, are polynomially equivalent
[Reckhow, PhD thesis, University of Toronto, 1976].</p>

<hr>

<p>Establishing lower bounds on Frege proofs could be viewed as a step towards proving <span class="math-container">$NP \neq coNP$</span>, since if this is true then no propositional proof system (including Frege) can have polynomial size proofs for all tautologies.</p>

CC BY-SA 4.0
2010-08-19T21:55:17.343Z
2019-09-22T12:53:13.703Z
2019-09-22T12:53:13.703Z
Iddo Tzameret
<blockquote>
  <p>Are there problems that cannot be solved efficiently by parallel computers?</p>
</blockquote>

<p>Problems that are P-complete are not known to be parallelizable.  P-complete problems include Horn-SAT and Linear Programming.  But proving that this is the case would require separating some notion of parallelizable problems (such as NC or LOGCFL) from P.</p>

<p>Computer processor designs are increasing the number of processing units, in the hope that this will yield improved performance.  If fundamental algorithms such as Linear Programming are inherently not parallelizable, then there are significant consequences.</p>

CC BY-SA 2.5
2010-08-24T06:33:59.913Z
I'm pretty sure that LP algorithms, as they stand today, are not parallelizable.  I believe they fit into Mulmuley's RAM-without-bit-operations model.  In http://dx.doi.org/10.1137/S0097539794282930 K. Mulmuley. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput. 28 (4), 1460-1509 (1999) he shows that $P \neq NC$ in that model, showing that many natural (usually numerical) algorithms for $P$-complete problems are not parallelizable.  This does not answer the question in the boolean case, but it does answer it for a large class of natural algorithms.
Joshua Grochow
CC BY-SA 2.5
2010-08-23T16:29:22.547Z
2010-08-23T16:29:22.547Z
András Salamon
<p>Can we compute the edit distance between two strings of length $n$ in sub-quadratic time, i.e., in time $O(n^{2-\epsilon})$ for some $\epsilon>0$ ?</p>

CC BY-SA 3.0
2015-10-11T01:36:12.137Z
Update (STOC 2015): Backurs and Indyk give evidence that better-than-quadratic time is not possible.  See https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/ .
Neal Young
CC BY-SA 2.5
2010-09-11T12:00:19.680Z
Do you have references for that? I actually thought that this proposition was trivially false although I can’t think of a proof off the top of my head. (Although I’m aware that the runtime can be made dependent on the number of errors.)
Konrad Rudolph
CC BY-SA 2.5
2010-08-25T19:40:48.960Z
2010-08-25T19:40:48.960Z
Piotr
<p>Are there truly subquadratic-time algorithms (meaning $O(n^{2-\delta})$ time for some constant $\delta&gt;0$) for <a href="http://maven.smith.edu/~orourke/TOPP/P11.html" rel="noreferrer">3SUM-hard Problems</a>?</p>

<p>In 2014, <a href="http://arxiv.org/abs/1404.0799" rel="noreferrer">Grønlund and Pettie</a> described a deterministic algorithm for 3SUM itself that runs in time $O(n^2/(\log n/\log \log n)^{2/3})$.  Although this is a major result, the improvement over $O(n^2)$ is only (sub)logarithmic.  Moreover, no similar subquadratic algorithms are known for most other 3SUM-hard problems.</p>

CC BY-SA 3.0
2011-11-10T04:40:01.877Z
I was under the impression that we do not have n^2 lower bound for any problem in NP.
Sariel Har-Peled
CC BY-SA 3.0
2012-11-28T02:14:13.440Z
@SarielHar-Peled That's an interested claim that I hadn't heard before. There are certainly problems in NP where the output is quadratic on the size of the input, and so a quadratic lower bound is trivial. Are you saying that we do not have a quadratic bound on, say, the max of the input and output sizes for a problem in NP? Or that we don't have a problem in NTIME($f(n)$) that is not in DTIME($o(f(n)^2)$)? I would love to see a source or further discussion of this.
William Macrae
CC BY-SA 3.0
2012-12-01T05:42:47.107Z
I had the distinct impression that if you are restricted to decision problems (no output arguments), then nothing is known. But you should really ask a complexity person.
Sariel Har-Peled
CC BY-SA 3.0
2014-07-07T17:33:49.097Z
[A recent arXiv paper](http://arxiv.org/abs/1404.0799) claims to have settled this conjecture by giving sub-quadratic algorithms for 3-SUM.
Mangara
CC BY-SA 2.5
2010-08-25T19:36:51.073Z
Good question. However, the existence of sub-quadratic algorithms for the 3SUM problem is wide open even for **randomized** algorithms. Of course, deterministic algorithm would have been even nicer..
Piotr
CC BY-SA 2.5
2010-08-25T20:34:30.303Z
In the quantum case, there are known matching n log(n) lower and upper bounds for 3SUM:

Andrej Dubrovsky, Oksana Scegulnaja-Dubrovska
Improved Quantum Lower Bounds for 3-Sum Problem.
Proceedings of Baltic DB&IS 2004, vol. 2, Riga, Latvia, pp.40-45.
Martin Schwarz
CC BY-SA 2.5
2010-08-25T20:42:43.360Z
@Piotr: Thanks! Have edited.
Aryabhata
CC BY-SA 2.5
2010-09-01T16:50:46.000Z
@Martin, that's quite interesting. I need to see what those upper bounds look like !
Suresh Venkat
CC BY-SA 3.0
2010-08-23T19:07:47.687Z
2015-06-25T22:40:24.090Z
2015-06-25T22:40:24.090Z
Aryabhata
<p>BQP = P?</p>

<p>Also: NP contained in BQP?</p>

<p>I know this violated the rules by having two questions in the answer, but when taken with the P vs NP question, they are not necessarily independent questions.</p>

CC BY-SA 2.5
2010-08-17T21:00:38.793Z
2010-08-17T21:00:38.793Z
Joe Fitzsimons
<ol>
<li> Isomorphism Conjecture.  (Are all NP-complete problems the "same" problem?)</li>
<li> Can cryptography be based upon an NP-complete problem?</li>

<br>and, a little further away from the mainstream:<br><br>

<li> What is the size of NP within EXP?</li>
</ol>

<p>(Informally, if you have all problems in EXP on a table, and you pick one up uniformly at random, what is the probability that the problem you chose is also in NP?  This question has been formalized by the notion of resource-bounded measure.  It is known that P has measure zero within EXP, i.e., the problem you picked up from the table is almost surely not in P.)</p>

CC BY-SA 3.0
2011-08-16T05:30:36.173Z
Would be nice to have a link to some info about the isomorphism conjecture
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-16T11:15:21.950Z
@Artem: you could start here: http://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html?m=1
Aaron Sterling
CC BY-SA 2.5
2010-08-17T17:48:51.747Z
Is this the same as p-measure in the Complexity Zoo?  Where would I go to read more about it?
András Salamon
CC BY-SA 2.5
2010-08-17T18:02:52.513Z
P-measure is one example of resource-bounded measure: more generally, you can imagine a machine trying to predict a sequence, and the computational resources it has available to do so are what provides the resource-bound on the measure.  I used p-measure in my informal explanation of EXP on a table.  For further reading, I recommend the journal version of the following survey by Lutz (the CZ cites the conference version of this survey).  http://www.cs.iastate.edu/~lutz/=PAPERS/qset.ps  (in postscript, I hope that's ok)
Aaron Sterling
CC BY-SA 2.5
2010-08-17T23:17:32.890Z
Thanks.  Here is a PDF of that paper for those who can't read PS: http://archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/TR96-08.pdf
András Salamon
CC BY-SA 2.5
2010-08-18T01:32:32.327Z
Interesting. Is it correct that NP not having measure 0 would imply P \neq NP? Would NP having measure 0 have any big implications?
Opt
CC BY-SA 2.5
2010-08-18T02:24:48.113Z
Yes to your first question.  P has measure 0 in EXP, so if NP does not, you get P != NP immediately.  For the second question, I suggest you read the last paragraph of page 28 in the survey Andras and I linked to.  (Not enough space in the comment to paste it here, sorry.)  Basically, if NP has measure zero, there exists an feasible algorithm that could guess membership in an NP-hard problem "unreasonably" well.  So it seems likely that NP is not measure zero within EXP.
Aaron Sterling
CC BY-SA 2.5
2010-08-17T17:34:36.903Z
2010-08-18T15:08:42.873Z
2010-08-18T15:08:42.873Z
Aaron Sterling
<p>What is the approximability of <a href="https://en.wikipedia.org/wiki/Traveling_salesman_problem#Metric_TSP" rel="nofollow noreferrer">Metric TSP</a>?  <a href="https://en.wikipedia.org/wiki/Christofides_algorithm" rel="nofollow noreferrer">Christofides' Algorithm</a> from 1975 is a polynomial-time (3/2)-approximation algorithm.  Is it NP-hard to do better?</p>
<ul>
<li><p>Approximating Metric TSP to within a factor smaller than 220/219 is NP-hard (Papadimitriou and Vempala, 2006 <a href="http://www.cs.berkeley.edu/%7Echristos/tsp.ps" rel="nofollow noreferrer">[PS]</a>).  To my knowledge this is the best known lower bound.</p>
</li>
<li><p>There is some evidence suggesting that the actual bound may be 4/3 (Carr and Vempala, 2004 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.7595" rel="nofollow noreferrer">[Free version]</a> <a href="https://doi.org/10.1007/s10107-004-0506-y" rel="nofollow noreferrer">[Good version]</a>).</p>
</li>
<li><p>The upper bound on approximability was recently lowered to <span class="math-container">$13/9$</span> (Mucha 2011 &quot;13/9
-approximation for Graphic TSP&quot; [<a href="https://arxiv.org/pdf/1108.1130.pdf" rel="nofollow noreferrer">PDF</a>])</p>
</li>
</ul>

CC BY-SA 3.0
2011-06-02T18:34:55.870Z
Metric TSP recently done by 3/2 - e where e is constant (near 0.002)
Saeed
CC BY-SA 3.0
2012-01-26T23:42:29.187Z
some discussion of [metric TSP on Godel's lost letter](http://rjlipton.wordpress.com/2011/12/03/the-meaning-of-omega/)
Artem Kaznatcheev
CC BY-SA 3.0
2012-05-17T11:50:10.137Z
@Saeed, did you mean the algorithm only for the special case of Metric TSP: for Graphic TSP? Then it was improved to 13/9 by Mucha. It seems that 3/2 is the best known upper bound for Metric TSP.
Alex Golovnev
CC BY-SA 3.0
2012-05-17T19:51:59.773Z
@AlexGolovnev, Hi Alex, Yes, but my comment was before the new paper coming ;) (I saw Oveis Gharan paper at that time).
Saeed
CC BY-SA 4.0
2010-08-19T13:23:45.993Z
2022-09-15T11:00:34.187Z
2022-09-15T11:00:34.187Z
James King
<h3>Give an explicit function with exponential circuit complexity.</h3>
<p>Shannon proved in 1949 that if you pick a Boolean function at random,
it has exponential circuit complexity with probability almost one.</p>
<p>The best lower bound for an explicit Boolean function  <span class="math-container">$f:\{0,1\}^n \to \{0,1\}$</span>
we have so far is <span class="math-container">$5n - o(n)$</span> by K. Iwama, O. Lachish, H. Morizumi, and R. Raz.</p>

CC BY-SA 2.5
2010-11-15T23:22:26.710Z
Is there a good exposition on Shannon's work?
Turbo
CC BY-SA 2.5
2010-11-16T19:19:25.710Z
The argument is detailed in the following lecture notes: http://www.math.tau.ac.il/~zwick/scribe-boolean.html
Marc
CC BY-SA 3.0
2017-01-06T21:31:29.863Z
This is an excellent problems and brings back fond memories of being assigned Shanon's result my second year of university.
Stella Biderman
CC BY-SA 4.0
2019-09-22T19:11:36.863Z
@RyanWilliams Is there explicit functions with general formula of superlinear size or  is it an open problem related to explicit functions with superlinear circuit complexity? DeMorgan formula superlinear functions are known,
VS.
CC BY-SA 4.0
2019-09-22T23:00:00.347Z
I'm not exactly sure what you're asking (you mention both formula and circuit complexity) but the best known formula lower bound over the basis of all 2-bit Boolean formulas is about $n^2$. For the DeMorgan basis it is about $n^3$. These are achieved by an explicit function (called Andreev's function).
Ryan Williams
CC BY-SA 2.5
2010-09-13T17:12:09.243Z
This way of stating the problem always bugs me, because you have to be careful about what you mean by "explicit". It is easy to write down a description of a function that has exponential circuit complexity. If "explicit" means "computable in exponential time or less", then I agree, this is a major open problem.
Ryan Williams
CC BY-SA 2.5
2010-09-14T12:05:36.970Z
Ryan, you are right. This is an extremely important point. It is also easy to write down a description of an uncomputable function. In the paper I cite, the lower bound is proved for a function that is constructible in deterministic polynomial time.
Marc
CC BY-SA 3.0
2010-09-05T21:18:31.880Z
2015-10-09T12:55:35.990Z
2020-06-17T09:38:08.363Z
Marc
<p>What is the query complexity of testing triangle-freeness in dense graphs (i.e., distinguishing triangle-free graphs from those $\epsilon$-far from being triangle-free)? The known upper bound is a tower of exponentials in $1/\epsilon$, while the known lower bound is only mildly superpolynomial in $1/\epsilon$.  This is a pretty basic question in extremal graph theory/additive combinatorics that has been open for nearly 30 years.</p>

CC BY-SA 2.5
2010-08-18T06:54:47.353Z
2010-08-18T07:17:00.653Z
2010-08-18T07:17:00.653Z
arnab
<p>Sensitivity versus block sensitivity</p>

<p>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.</p>

<p>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."</p>

CC BY-SA 4.0
2019-09-15T18:03:49.297Z
Now resolved! (should be removed?)
Joshua Grochow
CC BY-SA 2.5
2010-10-21T20:22:27.490Z
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".
Dana Moshkovitz
CC BY-SA 2.5
2010-08-17T20:10:24.293Z
2010-08-17T20:10:24.293Z
Ross Snider
<p>Is BQP in PH (polynomial hierachy)?                </p>

CC BY-SA 2.5
2010-08-18T01:34:55.237Z
2010-08-18T01:34:55.237Z
Opt
<p>Are NP-completeness in the sense of Cook and NP-completeness in the sense of Karp different concepts, assuming P $\neq$ NP?</p>

CC BY-SA 3.0
2013-09-08T18:43:57.183Z
2013-09-08T18:43:57.183Z
vb le
<p>Does there exist any hypothesis class that is NP-Hard to (improperly) PAC learn?</p>

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

CC BY-SA 2.5
2010-08-17T20:40:07.563Z
2010-10-15T22:31:19.953Z
2010-10-15T22:31:19.953Z
Lev Reyzin
<p>The "P vs NP" question extends naturally to polynomial-time hierarchy (PH): "Whether PH has infinite levels, or it collapses to some finite level?"</p>

<p>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.</p>

<p>Several other results follow from the infiniteness of the levels of PH.</p>

CC BY-SA 2.5
2010-09-05T13:33:15.910Z
2010-09-05T13:33:15.910Z
Sadeq Dousti
<p>What about proving BPP is contained in NP? (Unconditionally; we already know that BPP=P assuming pretty reasonable complexity assumptions)</p>

CC BY-SA 2.5
2010-10-17T01:35:43.793Z
2010-10-17T01:35:43.793Z
Dana Moshkovitz
<p>Is there an algorithm to compute the generalized star-height of a given regular language?</p>

<p>See <a href="http://en.wikipedia.org/wiki/Generalized_star_height_problem">http://en.wikipedia.org/wiki/Generalized_star_height_problem</a></p>

<p>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[&lt;].</p>

<p>It follows that there are languages of gsh $1$, like $(aa)^*$, but no language of gsh $&gt; 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
<a href="http://www.liafa.univ-paris-diderot.fr/~jep/Problemes/starheight.html">http://www.liafa.univ-paris-diderot.fr/~jep/Problemes/starheight.html</a> </p>

CC BY-SA 3.0
2013-08-08T13:58:26.347Z
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$?
Joshua Grochow
CC BY-SA 3.0
2013-08-09T22:54:24.727Z
@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$.
J.-E. Pin
CC BY-SA 3.0
2013-08-08T13:27:25.030Z
2013-08-08T13:27:25.030Z
J.-E. Pin
<blockquote>
  <p>Derandomization of the Polynomial Identity Testing problem</p>
</blockquote>

<p>The problem is the following: Given an <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity">arithmetic circuit</a> computing a polynomial $P$, is $P$ identically zero? </p>

<p>This problem can be solved in randomized polynomial time but is not known to be solvable in deterministic polynomial time.</p>

<p>Related is Shub and Smale's $\tau$ conjecture. Given a polynomial $P$, we define its $\tau$-complexity $\tau(P)$ as the size of the smallest arithmetic circuit computing $P$ using the sole constant $1$. For a univariate polynomial $P\in\mathbb Z[x]$, let $z(P)$ be its number of real roots.</p>

<blockquote>
  <p>Prove that there exists a universal constant $c$ such that for every $P\in\mathbb Z[x]$, $z(P)\le (1+\tau(P))^c$. </p>
</blockquote>

CC BY-SA 3.0
2011-11-03T21:27:14.987Z
2011-11-03T21:27:14.987Z
Bruno
<p><strong>Is the discrete logarithm problem in P?</strong></p>

<p>Let $G$ be a cyclic group of order $q$ and $g,h \in G$ such that $g$ is a generator of $G$. The problem of finding $n \in \mathbb{N}$ such that $g^n = h$ is known as the <em>discrete logarithm problem</em> (DLP). Is there a (classical) algorithm for solving the DLP in worst-case polynomial-time in the number of bits of $q$?</p>

<p>There are variations of DLP which are believed to be easier, but are still unsolved. The <em>computational Diffie-Hellman problem</em> (CDH) asks for finding $g^{a b}$ given $g, g^a$ and $g^b$. The <em>decisional Diffie-Hellman problem</em> (DDH) asks for deciding, given $g, g^a, g^b, h \in G$, if $g^{a b} = h$.</p>

<p>Clearly DLP is hard if CDH is hard, and CDH is hard if DDH is hard, but no converse reductions are known, except for some groups. The assumption that DDH is hard is key to the security of some cryptosystems, such as <a href="http://en.wikipedia.org/wiki/ElGamal" rel="noreferrer">ElGamal</a> and <a href="http://en.wikipedia.org/wiki/Cramer-Shoup_cryptosystem" rel="noreferrer">Cramer-Shoup</a>.</p>

CC BY-SA 4.0
2019-08-28T05:05:21.160Z
DLP was recently [put in quasi-P](https://eprint.iacr.org/2019/751) for the group $G = \mathbb{F}_{p^n}^\times$
Mark Schultz-Wu
CC BY-SA 2.5
2010-09-05T13:28:43.627Z
Well, we do know DLP is contained within BQP.
Joe Fitzsimons
CC BY-SA 3.0
2010-09-05T13:24:46.447Z
2015-10-11T20:07:57.880Z
2015-10-11T20:07:57.880Z
Felipe Lacerda
<p>I know the OP asked for only one problem per post, but the RTA (Rewriting Techniques and their Applications) <a href="http://rtaloop.mancoosi.univ-paris-diderot.fr/problems/summary.html">1</a> and TLCA (Typed Lambda Calculi and their Applications) conferences both maintain lists of open problems in their fields <a href="http://tlca.di.unito.it/opltlca/">2</a>.  These lists are quite useful, as they also include pointers to previous work done on attempting to solve these problems.</p>

CC BY-SA 2.5
2010-08-25T20:57:47.030Z
No problem.  Does anybody know of any other similar lists from other conferences?  They're quite interesting to read.
Dominic Mulligan
CC BY-SA 2.5
2010-08-24T09:03:39.320Z
2010-08-24T09:03:39.320Z
Dominic Mulligan
<p>The area of parameterized complexity has its own load of open problems.</p>

<p>Consider the decision problems</p>

<ul>
<li>given $(G,k)$ does there exist a vertex cover of size $k$ for the graph $G$?</li>
<li>given $(F,k)$ does there exist a satisfying assignment of weight $k$ for the formula $F$?</li>
<li>given $(G,k)$ does there exist a clique of size $k$ in a graph $G$?</li>
<li>etc...</li>
</ul>

<p>Many, MANY, combinatorial problems exist in this form.  Parameterized complexity 
consider an algorithm to be "efficient" if its running time is upper bounded by $f(k)n^c$ where $f$ is an arbitrary function and $c$ is a constant <strong>independent</strong> of $k$.  In comparison notice that all such problems can be easily solved in $n^{O(k)}$.</p>

<p>This framework models the cases in which we are looking for a small combinatorial structure and we can afford exponential run-time with respect to the size of the <strong>solution/witness</strong>.</p>

<p>A problem with such an algorithm (e.g. vertex cover) is called <em>Fixed Parameter Tractable</em> (FPT).</p>

<p>Parameterized complexity is a mature theory and has both strong theoretical foundations and appeal for practical applications.  Decision problems interesting for such theory form a very well structured hierarchy of classes with natural complete problems:</p>

<p>$$
FPT \subseteq W[1] \subseteq W[2] \subseteq \ldots \subseteq W[i] \subseteq W[i+1] \subseteq \ldots W[P]
$$</p>

<p>Of course it is open if any of such inclusion is strict or not. Notice that if $FPT=W[1]$ then SAT has subexponential algorithm (this is non trivial).  Last statement connects prameterized complexity with $ETH$ mentioned above.</p>

<p>Also notice that investigating such collapses is not an empty exercise: proving that $W[1]=FPT$ is equivalent to prove that there is a fixed parameter tractable algorithm for finding $k$-cliques.</p>

CC BY-SA 2.5
2010-10-21T19:46:16.310Z
2010-10-21T19:46:16.310Z
MassimoLauria
<p>Is there a Quantum PCP theorem?</p>

CC BY-SA 3.0
2015-06-25T22:55:03.673Z
I think this answer needs to be updated.
Kaveh
CC BY-SA 3.0
2015-06-26T01:17:28.097Z
@Kaveh: What would you like to see added?
Robin Kothari
CC BY-SA 3.0
2015-06-26T03:46:40.023Z
http://arxiv.org/abs/1309.7495
Kaveh
CC BY-SA 3.0
2015-06-26T03:54:36.407Z
http://arxiv.org/abs/1201.3387
Kaveh
CC BY-SA 3.0
2015-06-26T03:57:15.877Z
Essentially what is the closest thing we have so far and what are the main obstacles in the way of past attempts to prove/disprove it.
Kaveh
CC BY-SA 3.0
2015-06-26T04:53:18.893Z
https://www.youtube.com/watch?v=nrRPQ2EP3ms
Kaveh
CC BY-SA 3.0
2015-06-29T01:37:11.113Z
@Kaveh: I'm not too familiar with the advancements in the field. Maybe someone more knowledgeable can edit the post.
Robin Kothari
CC BY-SA 2.5
2010-08-18T11:35:12.203Z
This question was mentioned on Scott Aaronson's blog a while ago
http://scottaaronson.com/blog/?p=139
but I don't know if there has been any progress since.
Anthony Leverrier
CC BY-SA 2.5
2010-08-18T05:03:43.283Z
2010-08-18T05:03:43.283Z
Robin Kothari
<p>There are a lot of open problems in lambda calculi (typed and untyped).  See the <a href="http://tlca.di.unito.it/opltlca/">TLCA list of open problems</a> for details;  there is also a nice <a href="http://tlca.di.unito.it/opltlca/opltlca.pdf">PDF version</a> without the frames.</p>

<p>I particularly like problem #5:</p>

<blockquote>
  <p>Are there terms untypable in $F_ω$  but typable with help of positive recursive types? </p>
</blockquote>

CC BY-SA 2.5
2010-08-30T21:20:21.750Z
Thanks to Dominic Mulligan for pointing me to this particular list of problems.
Jacques Carette
CC BY-SA 2.5
2010-08-30T21:19:48.890Z
2010-08-30T21:19:48.890Z
Jacques Carette
<p>Parity games are two-player infinite-duration graph games, whose natural decision problem is in NP and co-NP, and whose natural search problem in PPAD and PLS.</p>

<p><a href="http://en.wikipedia.org/wiki/Parity_game">http://en.wikipedia.org/wiki/Parity_game</a></p>

<p>Can parity games be solved in polynomial time? </p>

<p>(More generally, a long-standing major open question in mathematical programming is whether P-matrix Linear Complementarity Problems can be solved in polynomial time?)</p>

CC BY-SA 2.5
2010-08-31T07:33:48.103Z
2010-09-01T06:52:30.383Z
2010-09-01T06:52:30.383Z
Rahul Savani
<p>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: <a href="http://cs.haifa.ac.il/~ronen/online_papers/online_papers.html" rel="noreferrer">http://cs.haifa.ac.il/~ronen/online_papers/online_papers.html</a></p>

CC BY-SA 3.0
2017-10-27T03:38:16.213Z
Could you link to one paper instead of a collection?
domotorp
CC BY-SA 2.5
2010-09-05T13:56:49.020Z
2010-09-05T13:56:49.020Z
Vincent Russo
<h2>Summary Table for Answers</h2>
<h3>Open Problems</h3>
<ul>
<li>Matrix Multiplication: <a href="https://cstheory.stackexchange.com/a/181/">Can multiplication of <span class="math-container">$n$</span> by <span class="math-container">$n$</span> matrices be done in <span class="math-container">$O(n^2)$</span> operations?</a></li>
<li>Graph Isomorphism: <a href="https://cstheory.stackexchange.com/a/218/">Is Graph Isomorphism in P?</a></li>
<li>Factoring: <a href="https://cstheory.stackexchange.com/a/216/">Is Factoring in P?</a></li>
<li>BPP vs. P: <a href="https://cstheory.stackexchange.com/a/176/">Is BPP = P?</a></li>
<li>Simplex: <a href="https://cstheory.stackexchange.com/a/473/">Is there a pivoting rule for the simplex algorithm that yields worst-case polynomial running time?</a></li>
<li>ETH: <a href="https://cstheory.stackexchange.com/a/205/">Is the Exponential Time Hypothesis true?</a></li>
<li>Logic for P: <a href="https://cstheory.stackexchange.com/a/251/">Is there a logic that captures P?</a></li>
<li>UGC: <a href="https://cstheory.stackexchange.com/a/183/">Is the Unique Games Conjecture true?</a></li>
<li>Perm vs. Det: <a href="https://cstheory.stackexchange.com/a/198/">Permanent vs. Determinant</a></li>
<li>FFT: <a href="https://cstheory.stackexchange.com/a/248/">Can we compute the FFT in much less than <span class="math-container">$O(n\log n)$</span> time?</a></li>
<li>Splay Trees: <a href="https://cstheory.stackexchange.com/a/201/">Is the Dynamic Optimality Conjecture for Splay Trees true?</a></li>
<li>NP vs. coNP: <a href="https://cstheory.stackexchange.com/a/197/">Is NP = coNP?</a></li>
<li>MST: <a href="https://cstheory.stackexchange.com/a/244/">Is there a linear time deterministic algorithm for the minimum spanning tree problem?</a></li>
<li>Frege: <a href="https://cstheory.stackexchange.com/a/341/">Do all propositional tautologies have polynomial-size Frege proofs?</a></li>
<li>NC vs. P: <a href="https://cstheory.stackexchange.com/a/416/">Are there problems that cannot be solved efficiently by parallel computers?</a></li>
<li>3SUM: <a href="https://cstheory.stackexchange.com/a/421/">Are there truly subquadratic-time algorithms for 3SUM-hard Problems?</a></li>
<li>Edit Distance: <a href="https://cstheory.stackexchange.com/a/582/">Can we compute the edit distance between two strings of length n in sub-quadratic time</a></li>
<li>BQP vs. P: <a href="https://cstheory.stackexchange.com/a/207/">Is BQP = P?</a></li>
<li>Isomorphism Conjecture: <a href="https://cstheory.stackexchange.com/a/179/">Are all NP-complete problems isomorphic?</a></li>
<li>Crypo. using NPC: <a href="https://cstheory.stackexchange.com/a/179/">Can cryptography be based upon an NP-complete problem?</a></li>
<li>Density of NP in EXP: <a href="https://cstheory.stackexchange.com/a/179/">What is the probability that an EXP problem is in NP?</a></li>
<li>NP vs. P/poly: <a href="https://cstheory.stackexchange.com/a/1004/">Is there an explicit problem requiring superpolynomial circuit size?</a></li>
<li>Triangle-freeness: <a href="https://cstheory.stackexchange.com/a/249/">What is the query complexity of testing triangle-freeness in dense graphs?</a></li>
<li>NEXP vs. BPP: <a href="https://cstheory.stackexchange.com/a/2242/">Is NEXP = BPP?</a></li>
<li>Metric TSP: <a href="https://cstheory.stackexchange.com/a/312/">What is the approximability of Metric TSP?</a></li>
<li>PIT: <a href="https://cstheory.stackexchange.com/a/8807/">Can we derandomize the Polynomial Identity Testing problem?</a></li>
<li>Quantum PCP: <a href="https://cstheory.stackexchange.com/a/243/">Is there a Quantum PCP theorem?</a></li>
<li>Typability of <span class="math-container">$F_\omega$</span>: <a href="https://cstheory.stackexchange.com/a/775/">Are there terms untypable in <span class="math-container">$F_\omega$</span> but typable with help of positive recursive types?</a></li>
<li>Parity Games: <a href="https://cstheory.stackexchange.com/a/789/">Can parity games be solved in polynomial time?</a></li>
<li>Sensitivity: <s><a href="https://cstheory.stackexchange.com/a/196/">Is sensitivity polynomially related to block sensitivity?</a></s> (<a href="https://arxiv.org/abs/1907.00847" rel="noreferrer">solved</a>)</li>
<li>Discrete Log: <a href="https://cstheory.stackexchange.com/a/997/">Is the Discrete Log problem in P?</a></li>
<li>W<a href="https://cstheory.stackexchange.com/a/181/">1</a> vs. FTP: <a href="https://cstheory.stackexchange.com/a/2369/">Is W[1] = FTP?</a></li>
<li>PH vs. BQP:<a href="https://cstheory.stackexchange.com/a/223/">Is BQP in PH?</a></li>
<li>Learning: <a href="https://cstheory.stackexchange.com/a/203/">Is there any hypothesis class that is NP-Hard to (improperly) PAC learn?</a></li>
<li>Cook vs. Karp: <a href="https://cstheory.stackexchange.com/a/18922/">Is NP-complete w.r.t. Cook reductions the same as NP-complete w.r.t. Karp reductions?</a></li>
<li>PH: <a href="https://cstheory.stackexchange.com/a/998/">Does Polynomial Hierarchy collapse?</a></li>
</ul>
<h3>Open Problem Lists</h3>
<ul>
<li><a href="http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science" rel="noreferrer">Open Problem Garden</a></li>
<li><a href="http://tlca.di.unito.it/opltlca/" rel="noreferrer">TLCA list of open problems</a></li>
</ul>

CC BY-SA 3.0
2015-10-11T19:40:32.420Z
The number of answers spans over a page. I think a list of responses (similar to [other big-list questions](http://cstheory.stackexchange.com/a/237/)) would be useful.
Kaveh
CC BY-SA 4.0
2015-10-11T19:18:19.220Z
2020-02-10T13:30:31.563Z
2020-06-17T09:38:08.363Z
Kaveh
<p><a href="http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science">Open Problem Garden</a> hosts a number of unsolved problems in theoretical computer science.</p>

CC BY-SA 2.5
2010-09-05T10:09:06.033Z
Could you find examples of major open problems that we don't have on this list yet, and post them as separate answers?
Jukka Suomela
CC BY-SA 2.5
2010-09-05T13:53:32.920Z
Sure Jukka you got it.
Vincent Russo
CC BY-SA 2.5
2010-09-05T03:15:55.840Z
2010-09-13T14:02:31.080Z
2010-09-13T14:02:31.080Z
Vincent Russo
<p>Another open problem for the lambda calculus (from <a href="http://tlca.di.unito.it/opltlca/">TLCA list of open problems</a>; <a href="http://tlca.di.unito.it/opltlca/opltlca.pdf">PDF version</a> ).</p>

<p>Problem #22 on the list:</p>

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

CC BY-SA 2.5
2010-08-30T21:22:45.567Z
2010-08-30T21:22:45.567Z
Jacques Carette
<p>Proving the existence of hard-on-average problems in NP using the P≠NP assumption.</p>

<p>Bogdanov and Trevisan, Average-Case Complexity, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106</p>

CC BY-SA 3.0
2012-06-08T23:56:28.897Z
Actually, proving the existence of hard-on-average problems in NP based on any reasonable assumption would be great.
Or Meir
CC BY-SA 3.0
2015-02-05T07:32:03.273Z
Is this related to the existance of one-way functions?
Zsbán Ambrus
CC BY-SA 3.0
2011-10-29T21:11:11.053Z
2011-10-29T21:11:11.053Z
Mohammad Al-Turkistany
<p>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. </p>

<p>This conjecture is known as the <a href="http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture">Aanderaa-Karp-Rosenberg conjecture</a>. </p>

CC BY-SA 2.5
2010-09-07T17:38:13.880Z
2010-09-10T04:40:12.617Z
2010-09-10T04:40:12.617Z
Gil Kalai
<p><a href="http://en.wikipedia.org/wiki/K-server_problem">K-server conjecture</a> and randomized K-server conjecture. </p>

<p>Definition according to wikipedia</p>

<p>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.</p>

CC BY-SA 3.0
2010-09-14T02:25:24.407Z
2012-01-26T23:49:14.653Z
2012-01-26T23:49:14.653Z
Ashwinkumar B V
<p>It seems strange to me that almost all the answers are about computational complexity, while the question asks for problems in all computer science.</p>

<p>To counter-balance a little bit: </p>

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

<p>Recent progress has been made, it has been showed decidable for $k=2$ in a 2014 <a href="http://www.labri.fr/perso/tplace/Files/PZ-ICALP14.pdf">paper</a> by Thomas Place and Marc Zeitoun, but the  general problem is still wide open.</p>

CC BY-SA 3.0
2014-07-23T09:16:17.747Z
2014-07-23T09:16:17.747Z
Denis
<p>Algebraic dichotomy conjecture (Bulatov, Jeavons and Krokhin): Assuming ETH, every constraint satisfaction problem is either in $P$ or requires $2^{
\Omega(n)}$ time.</p>

CC BY-SA 2.5
2010-11-13T20:46:37.640Z
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.
András Salamon
CC BY-SA 2.5
2010-11-12T23:42:36.417Z
2010-11-12T23:42:36.417Z
Mohammad Al-Turkistany
<p>Is Quasi-Polynomial Time in PSPACE? </p>

CC BY-SA 3.0
2015-02-14T01:23:12.217Z
http://cstheory.stackexchange.com/questions/8598/is-quasi-polynomial-time-in-pspace
got trolled too much this week
CC BY-SA 3.0
2012-01-26T21:06:15.500Z
2012-01-26T21:06:15.500Z
Tayfun Pay
<p>Can we multiply two arbitrary <span class="math-container">$n$</span>-bit numbers in <span class="math-container">$O(n)$</span> time? There is a trivial lower bound of <span class="math-container">$\Omega(n)$</span>, but no better lower bound is known. Currently, the asymptotically fastest algorithm is <span class="math-container">$O(n \log n)$</span> - a recent breakthrough by <a href="https://hal.archives-ouvertes.fr/hal-02070778" rel="nofollow noreferrer">Harvey and van der Hoeven 2019</a>. The previous best took time <span class="math-container">$O(n \log n 2^{\log^* n})$</span> <a href="https://doi.org/10.1137/070711761" rel="nofollow noreferrer">due to Martin Fürer</a>, building off of the <a href="https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" rel="nofollow noreferrer">original algorithm by Schönhage–Strassen</a> which ran in <span class="math-container">$\Theta(n \log n \log \log n)$</span> time. <a href="https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/" rel="nofollow noreferrer">Regan and Lipton showed</a> that a super-linear lower bound would follow from the Hartmanis-Stearns Real-Time Computability Conjecture. </p>

<p>A <a href="http://drops.dagstuhl.de/opus/volltexte/2019/10586/" rel="nofollow noreferrer">recent result of Afshani, Freksen, Kamma, and Larsen</a> established the following conditional lower bound: assuming the network coding conjecture, any constant-degree Boolean circuit for multiplication must have size <span class="math-container">$\Omega(n\log n)$</span>.</p>

CC BY-SA 3.0
2014-03-03T15:03:29.657Z
This is a clearer exposition than an earlier version of the question by J.A from 2012.
András Salamon
CC BY-SA 3.0
2014-09-18T19:52:58.577Z
Maybe "asymptotically fastest" was a typo when referring to Schonhage-Strassen (since you then cite Furer's algorithm which is asymptotically faster...)?
Joshua Grochow
CC BY-SA 4.0
2019-09-15T19:34:38.190Z
Wouldn't it be good to mention the recent (conditional) lower bound based on the [network coding conjecture](https://arxiv.org/abs/1902.10935)? @JoshuaGrochow
Clement C.
CC BY-SA 4.0
2019-09-16T02:09:38.640Z
@ClementC. Is network coding complexity theoretic?
Turbo
CC BY-SA 4.0
2019-09-16T02:11:24.647Z
@ClementC.: Oh yeah, I forgot, good idea. I can't do it right now (you may be able to get to the edit before I do).
Joshua Grochow
CC BY-SA 4.0
2019-09-16T02:11:44.573Z
@T.... The lower bound is. "Assuming [conjecture], any constant degree boolean circuit for multiplication must have size $\Omega(n\log n)$."
Clement C.
CC BY-SA 4.0
2019-09-16T22:44:34.037Z
@ClementC. Seems as good a statement as 'if superconcentrators of such properties exist then certain matrices are rigid'.
Turbo
CC BY-SA 4.0
2019-09-17T00:23:28.757Z
I'm not sure what to say or reply to this. Maybe read the linked paper?
Clement C.
CC BY-SA 4.0
2019-09-17T01:52:42.727Z
I am not buying this as evidence for superlinear circuit complexity. That is what I mean.
Turbo
CC BY-SA 4.0
2014-03-03T09:36:32.390Z
2019-09-16T02:17:29.290Z
2019-09-16T02:17:29.290Z
Arindam Pal
<ul>
<li>Do a pseudo-randomized numbers generator exist?</li>
</ul>

CC BY-SA 3.0
2012-01-27T05:12:26.603Z
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.
Jalaj
CC BY-SA 4.0
2010-10-17T11:07:20.607Z
2019-09-22T11:18:13.640Z
2019-09-22T11:18:13.640Z
rursw1
<p>Some open problems in complexity theory lower bounds, together with their relationships, are mapped <a href="http://eccc.hpi-web.de/report/2013/119/">here</a>.</p>

CC BY-SA 3.0
2014-03-03T01:07:36.210Z
nice, useful, detailed, how about more of a summary/abstract on the misc relationships covered (which isnt really in the abstract either)
vzn
CC BY-SA 3.0
2014-03-02T12:37:29.060Z
2014-03-02T12:37:29.060Z
Manu
<p>If P != NP, Does the polynomial hierarchy collapse?</p>

<p>(Because if P = NP then it completely collapses, of course)</p>

CC BY-SA 3.0
2010-10-17T11:15:49.490Z
2011-10-30T08:52:55.837Z
2011-10-30T08:52:55.837Z
rursw1
<p>Finding natural SampNP-complete distributional problems.</p>

<p>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:<a href="http://dx.doi.org/10.1016/0022-0000%2892%2990019-F" rel="nofollow">10.1016/0022-0000(92)90019-F</a>). 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. </p>

CC BY-SA 3.0
2012-06-09T00:07:29.490Z
2014-02-28T21:28:02.523Z
2014-02-28T21:28:02.523Z
Or Meir
<blockquote>
  <p>Getting an O(1) factor approximation algorithm in polytime for the Maximum Independent Set of Rectangles. </p>
</blockquote>

<p>This is one of the biggest open problems in Computational Geometry. Recently, Anna Adamaszek and Andreas Wiese [1] 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)$ [2]. More recently, Abed et al. [3] have given a constant factor approximation based on a conjecture. </p>

<p>[1] <a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=6686176" rel="noreferrer">http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=6686176</a></p>

<p>[2] <a href="http://ttic.uchicago.edu/~cjulia/papers/rectangles-SODA.pdf" rel="noreferrer">http://ttic.uchicago.edu/~cjulia/papers/rectangles-SODA.pdf</a></p>

<p>[3] <a href="http://drops.dagstuhl.de/opus/volltexte/2015/5291/pdf/1.pdf" rel="noreferrer">http://drops.dagstuhl.de/opus/volltexte/2015/5291/pdf/1.pdf</a></p>

CC BY-SA 3.0
2015-10-10T23:50:06.433Z
2015-10-10T23:50:06.433Z
Sayan Bandyapadhyay
<p><strong>Conjunctive query containment over bag semantics</strong></p>

<p><em>In a <a href="http://www.googlefight.com/" rel="nofollow">GoogleFight</a> between two search queries, can one tell if the first query always wins, without looking at the data?</em></p>

<hr>

<p>This 1993 question from database theory [1] asks whether it is possible to decide if an SQL query (more precisely, a <a href="http://en.wikipedia.org/wiki/Conjunctive_query" rel="nofollow">conjunctive query</a>) 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.</p>

<p>One can also formalise the question without referring to databases (see also [2]):</p>

<blockquote>
  <p><strong>Homomorphism Domination</strong><br>
  <strong>Input:</strong> finite relational structures $S$ and $S'$.<br>
  <strong>Question:</strong> 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$?</p>
</blockquote>

<p>Since the quantification is over an infinite set of structures $T$, this may be undecidable.  It is known to be NP-hard [3] as a special case of a more general question over positive <a href="http://en.wikipedia.org/wiki/Semiring" rel="nofollow">semirings</a> (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 <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow">Hilbert's 10th problem</a> [4,5].</p>

<p>What makes this question interesting is that for most positive semirings of interest the general question <em>is</em> 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?  <a href="http://en.wikipedia.org/wiki/Ashok_K._Chandra" rel="nofollow">Ashok Chandra</a> and Philip Merlin showed in 1977 [6] 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.</p>

<p>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.</p>

<hr>

<p><em>Edit:</em> added some key references as requested by Sylvain.</p>

<ol>
<li>Surajit Chaudhuri and Moshe Y. Vardi, <em>Optimization of</em> Real <em>Conjunctive Queries</em>, PODS 1993, 59–70. doi:<a href="http://dx.doi.org/10.1145/153850.153856" rel="nofollow">10.1145/153850.153856</a></li>
<li>Swastik Kopparty and Benjamin Rossman, <em>The homomorphism domination exponent</em>, EJOC 2011, <strong>32</strong>(7) 1097–1114.  doi:<a href="http://dx.doi.org/10.1016/j.ejc.2011.03.009" rel="nofollow">10.1016/j.ejc.2011.03.009</a></li>
<li>Egor V. Kostylev, Juan L. Reutter, and András Z. Salamon, <em>Classification of Annotation Semirings over Containment of Conjunctive Queries</em>, TODS 2014, <strong>39</strong>(1) 1:1–39.  doi:<a href="http://dx.doi.org/10.1145/2556524" rel="nofollow">10.1145/2556524</a></li>
<li>Yannis E. Ioannidis and Raghu Ramakrishnan, <em>Containment of conjunctive queries: beyond relations as sets</em>, TODS 1995, <strong>20</strong>(3) 288–324.  doi:<a href="http://dx.doi.org/10.1145/211414.211419" rel="nofollow">10.1145/211414.211419</a></li>
<li>T.S. Jayram, Phokion G. Kolaitis, and Erik Vee, <em>The containment problem for</em> Real <em>conjunctive queries with inequalities</em>, PODS 2006, 80–89.  doi:<a href="http://dx.doi.org/10.1145/1142351.1142363" rel="nofollow">10.1145/1142351.1142363</a></li>
<li>Ashok K. Chandra and Philip M. Merlin, <em>Optimal Implementation of Conjunctive Queries in Relational Data Bases</em>, STOC 1977, 77–90.  doi:<a href="http://dx.doi.org/10.1145/800105.803397" rel="nofollow">10.1145/800105.803397</a></li>
</ol>

CC BY-SA 3.0
2014-02-28T21:44:05.897Z
Nice one.  Could you provide more links to the literature, on decidable cases etc. ?
Sylvain
CC BY-SA 3.0
2014-02-28T23:36:24.443Z
@Sylvain: as is usual here, I have avoided linking directly to my own work but our TODS 2014 paper has all the key links.
András Salamon
CC BY-SA 3.0
2014-03-01T15:52:31.753Z
Since I'm not bound by such usage habits, here is a link for others who might be interested: http://tods.acm.org/accepted/2013/SalamonClassification.pdf.  You could however provide a link to the PODS 1993 Chaudhuri & Vardi paper at http://dx.doi.org/10.1145/153850.153856 without being suspected of self-promotion.
Sylvain
CC BY-SA 3.0
2014-02-28T17:56:57.887Z
2014-03-01T16:49:26.337Z
2014-03-01T16:49:26.337Z
András Salamon
<p>Is $\mathsf{L}=\mathsf{NL}$? What about non-uniform versions? </p>

CC BY-SA 3.0
2012-06-08T12:09:42.433Z
Links or references, please. When you edit, would you consider make it standard fonts like everybody else?
Nobody
CC BY-SA 3.0
2012-06-09T00:12:02.293Z
Please use regular fonts. and run a spell checker
Suresh Venkat
CC BY-SA 3.0
2012-06-08T10:37:51.503Z
2013-03-31T21:18:43.860Z
2013-03-31T21:18:43.860Z
Jeigh
<p>In general, what is the relationship between time and space complexity classes?</p>

<p>There are many unresolved questions such as:</p>

<ul>
<li><p>Is <span class="math-container">$PTIME = NLOGSPACE$</span>?</p></li>
<li><p>Is <span class="math-container">$PTIME = DLOGSPACE$</span>?</p></li>
<li><p>Is <span class="math-container">$PTIME = PSPACE$</span>?</p></li>
<li><p>Is <span class="math-container">$DSPACE(s(n)) \subseteq PTIME$</span> for some <span class="math-container">$s(n) = \omega(\log n)$</span>?</p></li>
<li><p>Is <span class="math-container">$DTIME(t(n)) \subseteq PSPACE$</span> for some super polynomial
function <span class="math-container">$t(n)$</span>?</p></li>
</ul>

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

<ul>
<li><p>Is <span class="math-container">$NSPACE(k \log(n)) \subseteq DTIME(n^{k - \varepsilon})$</span> for any <span class="math-container">$k$</span> and <span class="math-container">$\varepsilon &gt; 0$</span>?  <strong><em>(see conjecture from Kasai and Iwata 1985)</em></strong></p></li>
<li><p>Is <span class="math-container">$DTIME(n) \subseteq DTISP(poly(n), \frac{n}{\log n})$</span>? <strong><em>(simulation from Hopcroft, Paul, Valiant 1977 only seems to work with super polynomial time complexity)</em></strong></p></li>
<li><p>Is <span class="math-container">$NSPACE(\log(n)) \subseteq DTISP(poly(n), \log^2 n)$</span>? <strong><em>(simulation from Savitch's theorem only seems to work with super polynomial time complexity)</em></strong></p></li>
</ul>

CC BY-SA 4.0
2020-02-10T10:39:27.427Z
**Note:** Even $NPTIME$ has not been shown to be different from $DLOGSPACE$.
Michael Wehar
CC BY-SA 4.0
2020-02-10T10:45:17.187Z
There also are related questions involving $CFL$ and $DCFL$ along with time and space complexity classes.
Michael Wehar
CC BY-SA 4.0
2020-02-10T10:36:36.677Z
2020-02-10T10:42:40.947Z
2020-02-10T10:42:40.947Z
Michael Wehar
<p>Broadly what is the status of <span class="math-container">$GCD$</span>, modular inverse and extended <span class="math-container">$GCD$</span>?</p>
<p>Can we prove <span class="math-container">$GCD$</span> is not in <span class="math-container">$L$</span>?</p>

CC BY-SA 4.0
2024-06-26T16:10:19.633Z
2024-06-26T16:32:35.573Z
2024-06-26T16:32:35.573Z
Turbo
<p>Can inductive-recursive types be constructed in univalent models of type theory?</p>

<p>Recently, <a href="https://link.springer.com/chapter/10.1007/978-3-030-17127-8_17" rel="nofollow noreferrer">Hugunin (2019)</a> 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.</p>

<p>Some more open problems in type theory <a href="https://ncatlab.org/homotopytypetheory/show/open+problems" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2020-01-28T18:44:52.233Z
2020-01-28T18:44:52.233Z
xrq
<p>Wikipedia only lists two problems under <a href="http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science">"unsolved problems in computer science"</a>:</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/P_and_NP">P = NP?</a></li>
<li><a href="http://en.wikipedia.org/wiki/One-way_function">The existence of one-way functions</a></li>
</ul>

<p>What are other major problems that should be added to this list?</p>

<p>Rules:</p>

<ol>
<li>Only one problem per answer</li>
<li>Provide a brief description and any relevant links </li>
</ol>

CC BY-SA 4.0
2022-09-20T18:47:40.283Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/139337/discussion-on-question-by-shane-major-unsolved-problems-in-theoretical-computer).
Bjørn Kjos-Hanssen
<big-list><open-problem>
Major unsolved problems in theoretical computer science?
Shane
# Major unsolved problems in theoretical computer science?

(Asked by: username_0 on 2010-08-17)

Wikipedia only lists two problems under ["unsolved problems in computer science"](http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science):

* [P = NP?](http://en.wikipedia.org/wiki/P_and_NP)
* [The existence of one-way functions](http://en.wikipedia.org/wiki/One-way_function)

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

**Tags:** big-list, open-problem
> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/139337/discussion-on-question-by-shane-major-unsolved-problems-in-theoretical-computer).  

---

## 57 answers

### Answer by username_2 on 2010-08-17. Score: 152

> Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?

The exponent of the best known upper bound even has a special symbol, $\omega$. Currently $\omega$ is approximately 2.376, by the [Coppersmith-Winograd algorithm](http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm). A nice overview of the state of the art is Sara Robinson, [*Toward an Optimal Algorithm for Matrix Multiplication*](http://www.siam.org/news/news.php?id=174), SIAM News, 38(9), 2005.

**Update**: Andrew Stothers (in his 2010 [thesis](http://hdl.handle.net/1842/4734)) showed that $\omega < 2.3737$, which was improved by Virginia Vassilevska Williams (in a July 2014 [preprint](http://www.cs.berkeley.edu/%7Evirgi/matrixmult-f.pdf)) to $\omega < 2.372873$. These bounds were both obtained by a careful analysis of the basic Coppersmith-Winograd technique.

**Update** (Jan 30, 2014): François Le Gall has proved that $\omega < 2.3728639$ in a paper published in ISSAC 2014 ([arXiv preprint](http://arxiv.org/abs/1401.7714v1)).

**Update** (Nov 4, 2023): "[New Bounds for Matrix Multiplication: from Alpha to Omega](https://arxiv.org/abs/2307.07970)" proved that $\omega \leq 2.371552$.

> **Comments:**
> **username_7**: How about a modest and realistic goal of $O(n^2 \log n)$ or some other function between $n^{2+\epsilon}$ and $n^2$? After all it is expected that integer multiplication has the lower bound of $O(n \log n)$.  
> **username_2**: I'm not sure going from even $2+0.376$ to $2+\epsilon$ is regarded as a "modest and realistic goal", let alone then going below $2+\epsilon$.  But it would be great to see some progress, so give it a shot!  
> **username_8**: The matrix multiplication exponent is defined to be the smallest real number $\omega$ such that $O(n^{\omega+\epsilon})$ arithmetic operations suffice for all $\epsilon>0$. Probably a factor like $\log n$ should be expected.  
> **username_3**: Just adding for the sake of completeness wrt current knowledge that CW bound was bettered a few days ago by Virginia Williams. And as noted by many others in the community, Andrew Stothers had obtained his bound beating CW's around one year before Virginia. The current record is $O(n^{2.373})$  
> **username_4**: I will just let this here http://research.microsoft.com/en-us/um/people/kannan/papers/matrixmult.pdf  
> **username_2**: @JaimePardos: the full version of the approximate matrix multiplication paper you refer to is http://www.stanford.edu/class/ee378B/papers/drineas-kannan-mahoney-monte-carlo1.pdf which focuses on algorithms with few passes over the data, with a more generally useful analysis of running time.  TL;DR: matrix multiplication can be approximated for some kinds of matrices in $O(n^2)$ time.  
> **username_5**: Even more embarrassing that we don't know the optimal algorithms for smallish matrices. NSF/DARPA should really fund cranking these out on spare supercomputing cycles so the chip makers can start cranking out optimal 64 x 64 MATMUL accelerators. Also a low power 8x8 unit would be a killer application for Micron's new venture to sprinkle compute blocks around RAM.  
> **username_6**: @AndrásSalamon I think it is known time complexity has to be $\omega(n^2)$ since circuit complexity is at least this much (http://dl.acm.org/citation.cfm?id=509932 result by Raz).  

---

### Answer by username_9 on 2010-08-17. Score: 132

> Is Graph Isomorphism in P?

The complexity of Graph Isomorphism (GI) has been an open question for several decades. Stephen Cook mentioned it in his [1971 paper on NP-completeness of SAT](http://4mhz.de/cook.html).

Determining whether two graphs are isomorphic can usually be done quickly, for instance by software such as [`nauty`](http://cs.anu.edu.au/~bdm/nauty/) and [`saucy`](http://vlsicad.eecs.umich.edu/BK/SAUCY/). On the other hand, Miyazaki constructed [classes of instances](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.7911&rep=rep1&type=pdf) for which `nauty` provably requires exponential time.

Read and Corneil reviewed the many attempts to tackle the complexity of GI up to that point: [*The Graph Isomorphism Disease*](http://dx.doi.org/10.1002/jgt.3190010410), Journal of Graph Theory **1**, 339–363, 1977.

GI is not known to be in co-NP, but there is a simple randomized protocol for Graph Non-Isomorphism (GNI). So GI (= co-GNI) is therefore believed to be "close to" NP ${}\cap{}$ co-NP.

On the other hand, if GI is NP-complete, then the Polynomial Hierarchy collapses. So GI is unlikely to be NP-complete. (Boppana, Håstad, Zachos, [*Does co-NP Have Short Interactive Proofs?*](http://dx.doi.org/10.1016/0020-0190(87)90232-8), IPL **25**, 127–132, 1987)

Shiva Kintali has a [nice discussion](http://kintali.wordpress.com/2010/09/02/hardness-of-graph-isomorphism/) of the complexity of GI at his blog.

Laszlo Babai proved that [Graph Isomorphism is in quasipolynomial time](http://arxiv.org/abs/1512.03547).

> **Comments:**
> **username_12**: Please take a look at [this entry](http://cstheory.stackexchange.com/questions/1064/polynomial-time-algorithm-for-graph-isomorphism-testing) as well.  
> **username_5**: I cranked an exact lower bound for generic brute force automorphism detection. http://oeis.org/A186202 Much less than $n!$ but still exponential.  Hoping McKay will couple it to the Schrier-Sims for his latest incarnation of NAUTY to make it run on parallel hardware.  
> **username_10**: [Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.  
> **username_11**: The claim was restored : http://people.cs.uchicago.edu/~laci/update.html  

---

### Answer by username_9 on 2010-08-17. Score: 96

## Complexity of Factoring

Is [Factoring](http://en.wikipedia.org/wiki/Integer_factorization) in $\mathsf{P}$?

* [Consequences of Factoring being in P?](https://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p)
* [Are the problems PRIMES, FACTORING known to be P-hard?](https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard)
* [What are the consequences of factoring being NP-complete?](https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete)
* [P with integer factorization oracle](https://cstheory.stackexchange.com/questions/4765/p-with-integer-factorization-oracle)
* [Evidence for integer factorization is in P](https://mathoverflow.net/questions/79366/evidence-for-integer-factorization-is-in-p) (on [MO](https://mathoverflow.net/))

> **Comments:**
> **username_5**: Any good publications you know of that describe factoring or primality testing complexity in terms of the structure of the semigroup of addition and multiplication transforms on Z_n?  For example on $Z_3$  [0,1,2] is the +0|x1 transform, [1,2,0] is the +1 transform ...  

---

### Answer by username_13 on 2010-08-17. Score: 77

The problem of whether [P equals BPP](https://en.m.wikipedia.org/wiki/P_%3D_BPP_problem).

> **Comments:**
> **username_0**: This answer should be made CW now too...  
> **username_14**: and related questions like is NP = MA = AM?  
> **username_2**: See the closely related question http://cstheory.stackexchange.com/questions/64/what-specific-evidence-is-there-for-p-rp  

---

### Answer by username_15 on 2010-08-24. Score: 71

Is there a pivoting rule for the simplex algorithm that yields worst-case polynomial running time? More generally, is there any strongly polynomial algorithm for linear programming?

> **Comments:**
> **username_17**: I'll add to this question: would showing the nonexistence of strongly polynomial LP imply any class separation results?  
> **username_16**: ,,,and the Hirsch conjecture...  
> **username_2**: In 2011, Oliver Friedmann showed exponential lower bounds for many pivoting rules (he actually claims "essentially all natural" pivoting rules, including Random Facet and Random Edge).  These bounds apply when solving a linear program derived from 2-player parity games.  Friedmann's thesis http://edoc.ub.uni-muenchen.de/13294/ surveys the history in some depth (including various forms of the Hirsch Conjecture, and the 2010 counterexample to the strong form by Francisco Santos).  

---

### Answer by username_15 on 2010-08-17. Score: 69

The **exponential-time hypothesis (ETH)** asserts that solving SAT requires exponential, 2Ω(n) time. ETH implies many things, for instance that SAT is not in P, so ETH implies P ≠ NP. See Impagliazzo, Paturi, Zane, [*Which Problems Have Strongly Exponential Complexity?*](http://dx.doi.org/10.1006/jcss.2001.1774), JCSS 63, 512–530, 2001.

ETH is widely believed, but likely to be difficult to prove, as it implies many other complexity class separations.

> **Comments:**
> **username_18**: Seriously, I wouldn't call the ETH a major open problem at this point in time exactly because it implies P≠NP and thus is at least as difficult to prove.  
> **username_15**: No?  IMHO, your argument implies that ETH is even more of a major open problem than PvsNP.  
> **username_19**: Could you explain why $P \ne NP$ does not imply the ETH?  
> **username_15**: If $NP = PTIME(n^{\log n})$, then $P\ne NP$, but ETH is false.  
> **username_19**: Ah ok. But you mean DTIME($n^{\log n}$)?  

---

### Answer by username_18 on 2010-08-18. Score: 64

Immerman and Vardi show that fixed-point logic captures PTIME on the class of *ordered* structures. One of the biggest open problems in descriptive complexity theory is whether the dependency on the order can be removed:

> Is there a logic that captures PTIME?

Put simply, a logic capturing PTIME is a programming language for graph problems that works directly on the graph structure and does not have access to the encoding of the vertices and edges, such that the following hold:

1. any syntactically correct program models a polynomial-time computable graph problem and
2. any polynomial-time computable graph problem can be modelled by a syntactically correct program.

If there is no logic that captures PTIME, then $P \neq NP$ since NP is captured by existential second-order logic. A logic capturing PTIME would provide a possible attack to P vs NP.

See [Lipton's blog](http://rjlipton.wordpress.com/2010/04/05/graph-isomorphism-and-graph-minors/) for an informal discussion and *M. Grohe: [The Quest for a Logic Capturing PTIME](http://www-i7.informatik.rwth-aachen.de/~grohe/pub/gro08b.pdf)* (LICS 2008) for a more technical survey.

> **Comments:**
> **username_20**: Immerman-Vardi shows FO(LFP) captures logic on <i>ordered</i> structures, so this is a question about capturing PTIME on arbitrary finite models, I take it.  If I understand you correctly, isn't this question a translation of asking whether P != NP?  It might be more pointed to ask one or more of the open problems in the survey you link to.  Apologies if I am being clueless here.  
> **username_18**: Thanks, I edited the answer to mention Immerman-Vardi for clarification. No, this open problem is not known to be equivalent to P vs NP. The open problems in the survey are special cases of the big open problem and not appropriate in this thread. Maybe this reference is also helpful: http://rjlipton.wordpress.com/2010/04/05/graph-isomorphism-and-graph-minors/  

---

### Answer by username_21 on 2010-08-17. Score: 58

[Permanent](http://en.wikipedia.org/wiki/Permanent) versus [Determinant](http://en.wikipedia.org/wiki/Determinant)

The permanent versus determinant question is interesting because of two facts. First, the permanent of a matrix counts the number of perfect matchings in a bipartite graph. Therefore the permanent of such a matrix is #P-Complete. At the same time, the definition of the permanent is very close that of the determinant, ultimately different only because of a simple sign change. Determinant calculations are well known to be in P. Studying the different between the permanent and the determinant, and how many determinant calculations are required to compute the permanent speak about P versus #P.

> **Comments:**
> **username_22**: To me this doesn't qualify as a "major open problem", because the actual complexity theoretic question (do they have different complexities) is subsumed by P=NP (since #P is a superset of NP) and with that question set aside there isn't a concrete problem posed here.  
> **username_21**: I actually agree with this.  
> **username_23**: @DavidEppstein: Per v. det is closer to GapP v GapL, a counting analog of NP v NL. It's possible that $NL \neq P=NP$ and hence $GapP \neq GapL$. Also, per v det is much older than P v NP, essentially going back to [Polya 1913], in which he shows that one cannot affix signs to a matrix to change its permanent to its determinant (except 2x2). Valiant introduced a variant on those questions (allowing size of det to be larger than n) because of its significance in complexity, but even the pre-Valiant works give the motivation "because the permanent is so hard to compute..." (eg Gibson 1971)  
> **username_5**: What are the state of the art algorithms now for calculating the permanent of a 0-1 matrix? i.e. the number of legal permutation matrices you can generate from a subset of the 1's.  
> **username_24**: @ChadBrewbaker: see Mark Jerrum, Alistair Sinclair, Eric Vigoda, "A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Non-Negative Entries", *Journal of the ACM* 51/4 (2004), 671, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.116  

---

### Answer by username_25 on 2010-08-17. Score: 57

Is the [unique games conjecture](https://secure.wikimedia.org/wikipedia/en/wiki/Unique_games_conjecture) true?  
And: Given that there are [sub-exponential time approximation algorithms for Unique Games](http://www.cs.princeton.edu/~dsteurer/subexpug.pdf), where does the problem ultimately rest in terms of the complexity landscape?

> **Comments:**
> **username_2**: Would it not be more precise to say that if the UGC is _not_ true (i.e. unique games are not NP-hard, just harder than P), where would UGC fit into the landscape?  
> **username_25**: Oops. Yes, I should reword this. My intention was to highlight the the apparent discrepancy that results from unique games having a non-trivial approximation algorithm in sub-exponential (but not quite polynomial) time. More of: What does this say, if sub-exponential run time is optimal for unique games?  
> **username_25**: In retrospect, I thought I should include a pointer toward [this pre-print](http://eccc.hpi-web.de/report/2010/112/). In my opinion, it's as big of a development as the paper I have linked in the answer.  
> **username_26**: It's worth noting that there are no known hard instances of UCG. The current best approach works efficiently in every tested case. We just can't prove that we have found the most pathological examples.  

---

### Answer by username_15 on 2010-08-17. Score: 49

The [dynamic optimality conjecture for splay trees.](http://en.wikipedia.org/wiki/Splay_tree#Dynamic_optimality_conjecture)

Or more generally: Is *any* online dynamic binary search tree O(1)-competitive?

> **Comments:**
> **username_27**: pretty much that's it.  
> **username_28**: There are also the more recent [zipper trees](http://arxiv.org/abs/1003.0139), which are O(lg lg n) competitive without giving up O(lg n) worst-case access time.  

---

### Answer by username_27 on 2010-08-18. Score: 49

A linear time deterministic algorithm for the [minimum spanning tree](http://en.wikipedia.org/wiki/Minimum_spanning_tree) problem.


---

### Answer by username_29 on 2010-08-18. Score: 49

Can we compute the [FFT](http://en.wikipedia.org/wiki/Fft) in much less than $O(n \log n)$ time?

In the same (very) general vein, there are many questions of improving the run-times of many classical problems or algorithms: e.g., can [all-pairs-shortest-paths (APSP)](http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm) be solved in $O(n^{3-\epsilon})$ time ?

Edit: APSP runs in time $(\frac{n^3}{2^{\Omega(log n)^{1/2}}})$ "where additions and
comparisons of reals are unit cost (but all other operations have typical logarithmic cost)": <http://arxiv.org/pdf/1312.6680v2.pdf>

> **Comments:**
> **username_30**: An interesting development on FFT: "* An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and * An O(k log n log(n/k))-time algorithm for general input signals." source: http://arxiv.org/abs/1201.2501v1  

---

### Answer by username_21 on 2010-08-17. Score: 45

NP versus co-NP

The NP versus co-NP question is interesting because NP ≠ co-NP implies P ≠ NP (as P is closed under complement). It also relates to "duality": separation between finding/verifying examples and finding/verifying counterexamples. In fact, proving that a question is in both NP and co-NP is our first good evidence that a problem that seems to be outside of P is also likely not NP-Complete.

> **Comments:**
> **username_9**: This is also related to propositional proof complexity. There is a polynomial propositional proof system iff $NP$ is equal to $coNP$.  

---

### Answer by username_31 on 2010-08-19. Score: 42

> Do all propositional tautologies have polynomial-size Frege proofs?

**Arguably the major open problem of proof complexity**: demonstrate
super-polynomial size lower bounds on propositional proofs (called also Frege proofs).

Informally, a Frege proof system is just a standard propositional proof system for proving
propositional tautologies (one learns in a basic logic course), having axioms and deduction rules, where proof-lines are written as formulas. The *size* of
a Frege proof is the number of symbols it takes to write down the proof.

The problem then asks whether there is a family $(F\_n)\_{n=1}^\infty$ of propositional
tautological formulas for which there is no polynomial $ p $ such that the minimal Frege proof size of $ F\_n $ is at most $ p(|F\_n|)$, for all $ n=1,2,\ldots$ (where $ |F\_n| $ denotes the size of the formula $ F\_n $).

---

**Formal definition of a Frege proof system**

**Definition** (Frege rule) A *Frege rule* is a sequence of propositional
formulas $ A\_0(\overline x),\ldots,A\_k(\overline x) $, for $ k \le 0 $,
written as $ \frac{A\_1(\overline x), \ldots,A\_k(\overline
x)}{A\_0(\overline x)}$. In case $ k = 0 $, the Frege rule is called
an *axiom scheme*. A formula $ F\_0 $ is said to be *derived by the
rule* from $ F\_1,\ldots,F\_k $ if $ F\_0,\ldots,F\_k $ are all
substitution instances of $ A\_1,\ldots,A\_k $, for some assignment to
the $ \overline x $ variables (that is, there are formulas
$B\_1,\ldots,B\_n $ such that $F\_i = A\_i(B\_1/x\_1,\ldots,B\_n/x\_n), $ for
all $ i=0,\ldots,k $. The Frege rule is said to be *sound* if
whenever an assignment satisfies the formulas in the upper side
$A\_1,\ldots,A\_k $, then it also satisfies the formula in the lower
side $ A\_0 $.

**Definition** (Frege proof)
Given a set of Frege rules, a *Frege proof* is a sequence of
formulas such that every proof-line is either an axiom or was derived
by one of the given Frege rules from previous proof-lines. If the
sequence terminates with the formula $ A $, then the proof is said to
be *a proof of $ A $*. The **size** of a Frege proof is the the total sizes of
all the formulas in the proof.

A proof system is said to be *implicationally complete* if for
all set of formulas $ T $, if $ T $ semantically implies $ F $, then
there is a proof of $ F $ using (possibly) axioms from $ T $.
A proof system is said to be sound if it admits proofs of only
tautologies (when not using auxiliary axioms, like in the $ T $
above).

**Definition** (Frege proof system)
Given a propositional language and a finite set $ P $ of sound Frege rules,
we say that $ P $ is *a Frege proof system* if $ P $ is
implicationally complete.

Note that a Frege proof is always sound since the Frege rules are
assumed to be sound. We do not need to work with a specific Frege proof system, since a
basic result in proof complexity states that every two Frege proof
systems, even over different languages, are polynomially equivalent
[Reckhow, PhD thesis, University of Toronto, 1976].

---

Establishing lower bounds on Frege proofs could be viewed as a step towards proving $NP \neq coNP$, since if this is true then no propositional proof system (including Frege) can have polynomial size proofs for all tautologies.


---

### Answer by username_2 on 2010-08-23. Score: 41

> Are there problems that cannot be solved efficiently by parallel computers?

Problems that are P-complete are not known to be parallelizable. P-complete problems include Horn-SAT and Linear Programming. But proving that this is the case would require separating some notion of parallelizable problems (such as NC or LOGCFL) from P.

Computer processor designs are increasing the number of processing units, in the hope that this will yield improved performance. If fundamental algorithms such as Linear Programming are inherently not parallelizable, then there are significant consequences.

> **Comments:**
> **username_23**: I'm pretty sure that LP algorithms, as they stand today, are not parallelizable.  I believe they fit into Mulmuley's RAM-without-bit-operations model.  In http://dx.doi.org/10.1137/S0097539794282930 K. Mulmuley. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput. 28 (4), 1460-1509 (1999) he shows that $P \neq NC$ in that model, showing that many natural (usually numerical) algorithms for $P$-complete problems are not parallelizable.  This does not answer the question in the boolean case, but it does answer it for a large class of natural algorithms.  

---

### Answer by username_32 on 2010-08-25. Score: 39

Can we compute the edit distance between two strings of length $n$ in sub-quadratic time, i.e., in time $O(n^{2-\epsilon})$ for some $\epsilon>0$ ?

> **Comments:**
> **username_34**: Do you have references for that? I actually thought that this proposition was trivially false although I can’t think of a proof off the top of my head. (Although I’m aware that the runtime can be made dependent on the number of errors.)  
> **username_33**: Update (STOC 2015): Backurs and Indyk give evidence that better-than-quadratic time is not possible.  See https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/ .  

---

### Answer by username_35 on 2010-08-23. Score: 39

Are there truly subquadratic-time algorithms (meaning $O(n^{2-\delta})$ time for some constant $\delta>0$) for [3SUM-hard Problems](http://maven.smith.edu/~orourke/TOPP/P11.html)?

In 2014, [Grønlund and Pettie](http://arxiv.org/abs/1404.0799) described a deterministic algorithm for 3SUM itself that runs in time $O(n^2/(\log n/\log \log n)^{2/3})$. Although this is a major result, the improvement over $O(n^2)$ is only (sub)logarithmic. Moreover, no similar subquadratic algorithms are known for most other 3SUM-hard problems.

> **Comments:**
> **username_32**: Good question. However, the existence of sub-quadratic algorithms for the 3SUM problem is wide open even for **randomized** algorithms. Of course, deterministic algorithm would have been even nicer..  
> **username_38**: In the quantum case, there are known matching n log(n) lower and upper bounds for 3SUM:  Andrej Dubrovsky, Oksana Scegulnaja-Dubrovska Improved Quantum Lower Bounds for 3-Sum Problem. Proceedings of Baltic DB&IS 2004, vol. 2, Riga, Latvia, pp.40-45.  
> **username_35**: @Piotr: Thanks! Have edited.  
> **username_27**: @Martin, that's quite interesting. I need to see what those upper bounds look like !  
> **username_16**: I was under the impression that we do not have n^2 lower bound for any problem in NP.  
> **username_36**: @SarielHar-Peled That's an interested claim that I hadn't heard before. There are certainly problems in NP where the output is quadratic on the size of the input, and so a quadratic lower bound is trivial. Are you saying that we do not have a quadratic bound on, say, the max of the input and output sizes for a problem in NP? Or that we don't have a problem in NTIME($f(n)$) that is not in DTIME($o(f(n)^2)$)? I would love to see a source or further discussion of this.  
> **username_16**: I had the distinct impression that if you are restricted to decision problems (no output arguments), then nothing is known. But you should really ask a complexity person.  
> **username_37**: [A recent arXiv paper](http://arxiv.org/abs/1404.0799) claims to have settled this conjecture by giving sub-quadratic algorithms for 3-SUM.  

---

### Answer by username_39 on 2010-08-17. Score: 35

BQP = P?

Also: NP contained in BQP?

I know this violated the rules by having two questions in the answer, but when taken with the P vs NP question, they are not necessarily independent questions.


---

### Answer by username_20 on 2010-08-17. Score: 33

1. Isomorphism Conjecture. (Are all NP-complete problems the "same" problem?)
2. Can cryptography be based upon an NP-complete problem?
  
and, a little further away from the mainstream:  
  
3. What is the size of NP within EXP?

(Informally, if you have all problems in EXP on a table, and you pick one up uniformly at random, what is the probability that the problem you chose is also in NP? This question has been formalized by the notion of resource-bounded measure. It is known that P has measure zero within EXP, i.e., the problem you picked up from the table is almost surely not in P.)

> **Comments:**
> **username_2**: Is this the same as p-measure in the Complexity Zoo?  Where would I go to read more about it?  
> **username_20**: P-measure is one example of resource-bounded measure: more generally, you can imagine a machine trying to predict a sequence, and the computational resources it has available to do so are what provides the resource-bound on the measure.  I used p-measure in my informal explanation of EXP on a table.  For further reading, I recommend the journal version of the following survey by Lutz (the CZ cites the conference version of this survey).  http://www.cs.iastate.edu/~lutz/=PAPERS/qset.ps  (in postscript, I hope that's ok)  
> **username_2**: Thanks.  Here is a PDF of that paper for those who can't read PS: http://archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/TR96-08.pdf  
> **username_41**: Interesting. Is it correct that NP not having measure 0 would imply P \neq NP? Would NP having measure 0 have any big implications?  
> **username_20**: Yes to your first question.  P has measure 0 in EXP, so if NP does not, you get P != NP immediately.  For the second question, I suggest you read the last paragraph of page 28 in the survey Andras and I linked to.  (Not enough space in the comment to paste it here, sorry.)  Basically, if NP has measure zero, there exists an feasible algorithm that could guess membership in an NP-hard problem "unreasonably" well.  So it seems likely that NP is not measure zero within EXP.  
> **username_40**: Would be nice to have a link to some info about the isomorphism conjecture  
> **username_20**: @Artem: you could start here: http://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html?m=1  

---

### Answer by username_42 on 2010-08-19. Score: 31

What is the approximability of [Metric TSP](https://en.wikipedia.org/wiki/Traveling_salesman_problem#Metric_TSP)? [Christofides' Algorithm](https://en.wikipedia.org/wiki/Christofides_algorithm) from 1975 is a polynomial-time (3/2)-approximation algorithm. Is it NP-hard to do better?

* Approximating Metric TSP to within a factor smaller than 220/219 is NP-hard (Papadimitriou and Vempala, 2006 [[PS]](http://www.cs.berkeley.edu/%7Echristos/tsp.ps)). To my knowledge this is the best known lower bound.
* There is some evidence suggesting that the actual bound may be 4/3 (Carr and Vempala, 2004 [[Free version]](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.7595) [[Good version]](https://doi.org/10.1007/s10107-004-0506-y)).
* The upper bound on approximability was recently lowered to $13/9$ (Mucha 2011 "13/9
  -approximation for Graphic TSP" [[PDF](https://arxiv.org/pdf/1108.1130.pdf)])

> **Comments:**
> **username_43**: Metric TSP recently done by 3/2 - e where e is constant (near 0.002)  
> **username_40**: some discussion of [metric TSP on Godel's lost letter](http://rjlipton.wordpress.com/2011/12/03/the-meaning-of-omega/)  
> **username_44**: @Saeed, did you mean the algorithm only for the special case of Metric TSP: for Graphic TSP? Then it was improved to 13/9 by Mucha. It seems that 3/2 is the best known upper bound for Metric TSP.  
> **username_43**: @AlexGolovnev, Hi Alex, Yes, but my comment was before the new paper coming ;) (I saw Oveis Gharan paper at that time).  

---

### Answer by username_45 on 2010-09-05. Score: 30

### Give an explicit function with exponential circuit complexity.

Shannon proved in 1949 that if you pick a Boolean function at random,
it has exponential circuit complexity with probability almost one.

The best lower bound for an explicit Boolean function $f:\{0,1\}^n \to \{0,1\}$
we have so far is $5n - o(n)$ by K. Iwama, O. Lachish, H. Morizumi, and R. Raz.

> **Comments:**
> **username_47**: This way of stating the problem always bugs me, because you have to be careful about what you mean by "explicit". It is easy to write down a description of a function that has exponential circuit complexity. If "explicit" means "computable in exponential time or less", then I agree, this is a major open problem.  
> **username_45**: Ryan, you are right. This is an extremely important point. It is also easy to write down a description of an uncomputable function. In the paper I cite, the lower bound is proved for a function that is constructible in deterministic polynomial time.  
> **username_6**: Is there a good exposition on Shannon's work?  
> **username_45**: The argument is detailed in the following lecture notes: http://www.math.tau.ac.il/~zwick/scribe-boolean.html  
> **username_26**: This is an excellent problems and brings back fond memories of being assigned Shanon's result my second year of university.  
> **username_46**: @RyanWilliams Is there explicit functions with general formula of superlinear size or  is it an open problem related to explicit functions with superlinear circuit complexity? DeMorgan formula superlinear functions are known,  
> **username_47**: I'm not exactly sure what you're asking (you mention both formula and circuit complexity) but the best known formula lower bound over the basis of all 2-bit Boolean formulas is about $n^2$. For the DeMorgan basis it is about $n^3$. These are achieved by an explicit function (called Andreev's function).  

---

### Answer by username_48 on 2010-08-18. Score: 29

What is the query complexity of testing triangle-freeness in dense graphs (i.e., distinguishing triangle-free graphs from those $\epsilon$-far from being triangle-free)? The known upper bound is a tower of exponentials in $1/\epsilon$, while the known lower bound is only mildly superpolynomial in $1/\epsilon$. This is a pretty basic question in extremal graph theory/additive combinatorics that has been open for nearly 30 years.


---

### Answer by username_53 on 2011-11-03. Score: 27

> Derandomization of the Polynomial Identity Testing problem

The problem is the following: Given an [arithmetic circuit](http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity) computing a polynomial $P$, is $P$ identically zero?

This problem can be solved in randomized polynomial time but is not known to be solvable in deterministic polynomial time.

Related is Shub and Smale's $\tau$ conjecture. Given a polynomial $P$, we define its $\tau$-complexity $\tau(P)$ as the size of the smallest arithmetic circuit computing $P$ using the sole constant $1$. For a univariate polynomial $P\in\mathbb Z[x]$, let $z(P)$ be its number of real roots.

> Prove that there exists a universal constant $c$ such that for every $P\in\mathbb Z[x]$, $z(P)\le (1+\tau(P))^c$.


---

### Answer by username_54 on 2010-09-05. Score: 27

**Is the discrete logarithm problem in P?**

Let $G$ be a cyclic group of order $q$ and $g,h \in G$ such that $g$ is a generator of $G$. The problem of finding $n \in \mathbb{N}$ such that $g^n = h$ is known as the *discrete logarithm problem* (DLP). Is there a (classical) algorithm for solving the DLP in worst-case polynomial-time in the number of bits of $q$?

There are variations of DLP which are believed to be easier, but are still unsolved. The *computational Diffie-Hellman problem* (CDH) asks for finding $g^{a b}$ given $g, g^a$ and $g^b$. The *decisional Diffie-Hellman problem* (DDH) asks for deciding, given $g, g^a, g^b, h \in G$, if $g^{a b} = h$.

Clearly DLP is hard if CDH is hard, and CDH is hard if DDH is hard, but no converse reductions are known, except for some groups. The assumption that DDH is hard is key to the security of some cryptosystems, such as [ElGamal](http://en.wikipedia.org/wiki/ElGamal) and [Cramer-Shoup](http://en.wikipedia.org/wiki/Cramer-Shoup_cryptosystem).

> **Comments:**
> **username_39**: Well, we do know DLP is contained within BQP.  
> **username_55**: DLP was recently [put in quasi-P](https://eprint.iacr.org/2019/751) for the group $G = \mathbb{F}_{p^n}^\times$  

---

### Answer by username_56 on 2010-08-24. Score: 26

I know the OP asked for only one problem per post, but the RTA (Rewriting Techniques and their Applications) [1](http://rtaloop.mancoosi.univ-paris-diderot.fr/problems/summary.html) and TLCA (Typed Lambda Calculi and their Applications) conferences both maintain lists of open problems in their fields [2](http://tlca.di.unito.it/opltlca/). These lists are quite useful, as they also include pointers to previous work done on attempting to solve these problems.

> **Comments:**
> **username_56**: No problem.  Does anybody know of any other similar lists from other conferences?  They're quite interesting to read.  

---

### Answer by username_57 on 2010-10-21. Score: 26

The area of parameterized complexity has its own load of open problems.

Consider the decision problems

* given $(G,k)$ does there exist a vertex cover of size $k$ for the graph $G$?
* given $(F,k)$ does there exist a satisfying assignment of weight $k$ for the formula $F$?
* given $(G,k)$ does there exist a clique of size $k$ in a graph $G$?
* etc...

Many, MANY, combinatorial problems exist in this form. Parameterized complexity
consider an algorithm to be "efficient" if its running time is upper bounded by $f(k)n^c$ where $f$ is an arbitrary function and $c$ is a constant **independent** of $k$. In comparison notice that all such problems can be easily solved in $n^{O(k)}$.

This framework models the cases in which we are looking for a small combinatorial structure and we can afford exponential run-time with respect to the size of the **solution/witness**.

A problem with such an algorithm (e.g. vertex cover) is called *Fixed Parameter Tractable* (FPT).

Parameterized complexity is a mature theory and has both strong theoretical foundations and appeal for practical applications. Decision problems interesting for such theory form a very well structured hierarchy of classes with natural complete problems:

$$
FPT \subseteq W[1] \subseteq W[2] \subseteq \ldots \subseteq W[i] \subseteq W[i+1] \subseteq \ldots W[P]
$$

Of course it is open if any of such inclusion is strict or not. Notice that if $FPT=W[1]$ then SAT has subexponential algorithm (this is non trivial). Last statement connects prameterized complexity with $ETH$ mentioned above.

Also notice that investigating such collapses is not an empty exercise: proving that $W[1]=FPT$ is equivalent to prove that there is a fixed parameter tractable algorithm for finding $k$-cliques.


---

### Answer by username_14 on 2010-08-18. Score: 25

Is there a Quantum PCP theorem?

> **Comments:**
> **username_58**: This question was mentioned on Scott Aaronson's blog a while ago http://scottaaronson.com/blog/?p=139 but I don't know if there has been any progress since.  
> **username_9**: I think this answer needs to be updated.  
> **username_14**: @Kaveh: What would you like to see added?  
> **username_9**: http://arxiv.org/abs/1309.7495  
> **username_9**: http://arxiv.org/abs/1201.3387  
> **username_9**: Essentially what is the closest thing we have so far and what are the main obstacles in the way of past attempts to prove/disprove it.  
> **username_9**: https://www.youtube.com/watch?v=nrRPQ2EP3ms  
> **username_14**: @Kaveh: I'm not too familiar with the advancements in the field. Maybe someone more knowledgeable can edit the post.  

---

### Answer by username_59 on 2010-08-30. Score: 25

There are a lot of open problems in lambda calculi (typed and untyped). See the [TLCA list of open problems](http://tlca.di.unito.it/opltlca/) for details; there is also a nice [PDF version](http://tlca.di.unito.it/opltlca/opltlca.pdf) without the frames.

I particularly like problem #5:

> Are there terms untypable in $F\_ω$ but typable with help of positive recursive types?

> **Comments:**
> **username_59**: Thanks to Dominic Mulligan for pointing me to this particular list of problems.  

---

### Answer by username_60 on 2010-08-31. Score: 25

Parity games are two-player infinite-duration graph games, whose natural decision problem is in NP and co-NP, and whose natural search problem in PPAD and PLS.

<http://en.wikipedia.org/wiki/Parity_game>

Can parity games be solved in polynomial time?

(More generally, a long-standing major open question in mathematical programming is whether P-matrix Linear Complementarity Problems can be solved in polynomial time?)


---

### Answer by username_21 on 2010-08-17. Score: 23

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."

> **Comments:**
> **username_49**: 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".  
> **username_23**: Now resolved! (should be removed?)  

---

### Answer by username_41 on 2010-08-18. Score: 23

Is BQP in PH (polynomial hierachy)?


---

### Answer by username_50 on 2013-09-08. Score: 22

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


---

### Answer by username_51 on 2010-08-17. Score: 21

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>


---

### Answer by username_12 on 2010-09-05. Score: 19

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.


---

### Answer by username_49 on 2010-10-17. Score: 19

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


---

### Answer by username_52 on 2013-08-08. Score: 16

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

See <http://en.wikipedia.org/wiki/Generalized_star_height_problem>

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>

> **Comments:**
> **username_23**: 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$?  
> **username_52**: @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$.  

---

### Answer by username_59 on 2010-08-30. Score: 15

Another open problem for the lambda calculus (from [TLCA list of open problems](http://tlca.di.unito.it/opltlca/); [PDF version](http://tlca.di.unito.it/opltlca/opltlca.pdf) ).

Problem #22 on the list:

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


---

### Answer by username_64 on 2011-10-29. Score: 15

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

> **Comments:**
> **username_65**: Actually, proving the existence of hard-on-average problems in NP based on any reasonable assumption would be great.  
> **username_24**: Is this related to the existance of one-way functions?  

---

### Answer by username_66 on 2010-09-07. Score: 15

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](http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture).


---

### Answer by username_67 on 2010-09-14. Score: 15

[K-server conjecture](http://en.wikipedia.org/wiki/K-server_problem) 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.


---

### Answer by username_61 on 2010-09-05. Score: 14

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>

> **Comments:**
> **username_62**: Could you link to one paper instead of a collection?  

---

### Answer by username_9 on 2015-10-11. Score: 14

## Summary Table for Answers

### Open Problems

* Matrix Multiplication: [Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?](https://cstheory.stackexchange.com/a/181/)
* Graph Isomorphism: [Is Graph Isomorphism in P?](https://cstheory.stackexchange.com/a/218/)
* Factoring: [Is Factoring in P?](https://cstheory.stackexchange.com/a/216/)
* BPP vs. P: [Is BPP = P?](https://cstheory.stackexchange.com/a/176/)
* Simplex: [Is there a pivoting rule for the simplex algorithm that yields worst-case polynomial running time?](https://cstheory.stackexchange.com/a/473/)
* ETH: [Is the Exponential Time Hypothesis true?](https://cstheory.stackexchange.com/a/205/)
* Logic for P: [Is there a logic that captures P?](https://cstheory.stackexchange.com/a/251/)
* UGC: [Is the Unique Games Conjecture true?](https://cstheory.stackexchange.com/a/183/)
* Perm vs. Det: [Permanent vs. Determinant](https://cstheory.stackexchange.com/a/198/)
* FFT: [Can we compute the FFT in much less than $O(n\log n)$ time?](https://cstheory.stackexchange.com/a/248/)
* Splay Trees: [Is the Dynamic Optimality Conjecture for Splay Trees true?](https://cstheory.stackexchange.com/a/201/)
* NP vs. coNP: [Is NP = coNP?](https://cstheory.stackexchange.com/a/197/)
* MST: [Is there a linear time deterministic algorithm for the minimum spanning tree problem?](https://cstheory.stackexchange.com/a/244/)
* Frege: [Do all propositional tautologies have polynomial-size Frege proofs?](https://cstheory.stackexchange.com/a/341/)
* NC vs. P: [Are there problems that cannot be solved efficiently by parallel computers?](https://cstheory.stackexchange.com/a/416/)
* 3SUM: [Are there truly subquadratic-time algorithms for 3SUM-hard Problems?](https://cstheory.stackexchange.com/a/421/)
* Edit Distance: [Can we compute the edit distance between two strings of length n in sub-quadratic time](https://cstheory.stackexchange.com/a/582/)
* BQP vs. P: [Is BQP = P?](https://cstheory.stackexchange.com/a/207/)
* Isomorphism Conjecture: [Are all NP-complete problems isomorphic?](https://cstheory.stackexchange.com/a/179/)
* Crypo. using NPC: [Can cryptography be based upon an NP-complete problem?](https://cstheory.stackexchange.com/a/179/)
* Density of NP in EXP: [What is the probability that an EXP problem is in NP?](https://cstheory.stackexchange.com/a/179/)
* NP vs. P/poly: [Is there an explicit problem requiring superpolynomial circuit size?](https://cstheory.stackexchange.com/a/1004/)
* Triangle-freeness: [What is the query complexity of testing triangle-freeness in dense graphs?](https://cstheory.stackexchange.com/a/249/)
* NEXP vs. BPP: [Is NEXP = BPP?](https://cstheory.stackexchange.com/a/2242/)
* Metric TSP: [What is the approximability of Metric TSP?](https://cstheory.stackexchange.com/a/312/)
* PIT: [Can we derandomize the Polynomial Identity Testing problem?](https://cstheory.stackexchange.com/a/8807/)
* Quantum PCP: [Is there a Quantum PCP theorem?](https://cstheory.stackexchange.com/a/243/)
* Typability of $F\_\omega$: [Are there terms untypable in $F\_\omega$ but typable with help of positive recursive types?](https://cstheory.stackexchange.com/a/775/)
* Parity Games: [Can parity games be solved in polynomial time?](https://cstheory.stackexchange.com/a/789/)
* Sensitivity: ~~[Is sensitivity polynomially related to block sensitivity?](https://cstheory.stackexchange.com/a/196/)~~ ([solved](https://arxiv.org/abs/1907.00847))
* Discrete Log: [Is the Discrete Log problem in P?](https://cstheory.stackexchange.com/a/997/)
* W[1](https://cstheory.stackexchange.com/a/181/) vs. FTP: [Is W[1] = FTP?](https://cstheory.stackexchange.com/a/2369/)
* PH vs. BQP:[Is BQP in PH?](https://cstheory.stackexchange.com/a/223/)
* Learning: [Is there any hypothesis class that is NP-Hard to (improperly) PAC learn?](https://cstheory.stackexchange.com/a/203/)
* Cook vs. Karp: [Is NP-complete w.r.t. Cook reductions the same as NP-complete w.r.t. Karp reductions?](https://cstheory.stackexchange.com/a/18922/)
* PH: [Does Polynomial Hierarchy collapse?](https://cstheory.stackexchange.com/a/998/)

### Open Problem Lists

* [Open Problem Garden](http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science)
* [TLCA list of open problems](http://tlca.di.unito.it/opltlca/)

> **Comments:**
> **username_9**: The number of answers spans over a page. I think a list of responses (similar to [other big-list questions](http://cstheory.stackexchange.com/a/237/)) would be useful.  

---

### Answer by username_61 on 2010-09-05. Score: 13

[Open Problem Garden](http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science) hosts a number of unsolved problems in theoretical computer science.

> **Comments:**
> **username_63**: Could you find examples of major open problems that we don't have on this list yet, and post them as separate answers?  
> **username_61**: Sure Jukka you got it.  

---

### Answer by username_68 on 2014-07-23. Score: 10

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](http://www.labri.fr/perso/tplace/Files/PZ-ICALP14.pdf) by Thomas Place and Marc Zeitoun, but the general problem is still wide open.


---

### Answer by username_64 on 2010-11-12. Score: 8

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

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_69 on 2012-01-26. Score: 8

Is Quasi-Polynomial Time in PSPACE?

> **Comments:**
> **username_70**: http://cstheory.stackexchange.com/questions/8598/is-quasi-polynomial-time-in-pspace  

---

### Answer by username_71 on 2014-03-03. Score: 8

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](https://hal.archives-ouvertes.fr/hal-02070778). The previous best took time $O(n \log n 2^{\log^\* n})$ [due to Martin Fürer](https://doi.org/10.1137/070711761), building off of the [original algorithm by Schönhage–Strassen](https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm) which ran in $\Theta(n \log n \log \log n)$ time. [Regan and Lipton showed](https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/) 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](http://drops.dagstuhl.de/opus/volltexte/2019/10586/) 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)$.

> **Comments:**
> **username_2**: This is a clearer exposition than an earlier version of the question by J.A from 2012.  
> **username_23**: Maybe "asymptotically fastest" was a typo when referring to Schonhage-Strassen (since you then cite Furer's algorithm which is asymptotically faster...)?  
> **username_72**: Wouldn't it be good to mention the recent (conditional) lower bound based on the [network coding conjecture](https://arxiv.org/abs/1902.10935)? @JoshuaGrochow  
> **username_6**: @ClementC. Is network coding complexity theoretic?  
> **username_23**: @ClementC.: Oh yeah, I forgot, good idea. I can't do it right now (you may be able to get to the edit before I do).  
> **username_72**: @T.... The lower bound is. "Assuming [conjecture], any constant degree boolean circuit for multiplication must have size $\Omega(n\log n)$."  
> **username_6**: @ClementC. Seems as good a statement as 'if superconcentrators of such properties exist then certain matrices are rigid'.  
> **username_72**: I'm not sure what to say or reply to this. Maybe read the linked paper?  
> **username_6**: I am not buying this as evidence for superlinear circuit complexity. That is what I mean.  

---

### Answer by username_73 on 2010-10-17. Score: 7

* Do a pseudo-randomized numbers generator exist?

> **Comments:**
> **username_74**: 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.  

---

### Answer by username_75 on 2014-03-02. Score: 6

Some open problems in complexity theory lower bounds, together with their relationships, are mapped [here](http://eccc.hpi-web.de/report/2013/119/).

> **Comments:**
> **username_76**: nice, useful, detailed, how about more of a summary/abstract on the misc relationships covered (which isnt really in the abstract either)  

---

### Answer by username_73 on 2010-10-17. Score: 6

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

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


---

### Answer by username_65 on 2012-06-09. Score: 6

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](http://dx.doi.org/10.1016/0022-0000%2892%2990019-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.


---

### Answer by username_77 on 2015-10-10. Score: 5

> 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 [1] 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)$ [2]. More recently, Abed et al. [3] have given a constant factor approximation based on a conjecture.

[1] <http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6686176>

[2] <http://ttic.uchicago.edu/~cjulia/papers/rectangles-SODA.pdf>

[3] <http://drops.dagstuhl.de/opus/volltexte/2015/5291/pdf/1.pdf>


---

### Answer by username_2 on 2014-02-28. Score: 1

**Conjunctive query containment over bag semantics**

*In a [GoogleFight](http://www.googlefight.com/) between two search queries, can one tell if the first query always wins, without looking at the data?*

---

This 1993 question from database theory [1] asks whether it is possible to decide if an SQL query (more precisely, a [conjunctive query](http://en.wikipedia.org/wiki/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 [2]):

> **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 [3] as a special case of a more general question over positive [semirings](http://en.wikipedia.org/wiki/Semiring) (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](http://en.wikipedia.org/wiki/Hilbert%27s_tenth_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](http://en.wikipedia.org/wiki/Ashok_K._Chandra) and Philip Merlin showed in 1977 [6] 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](http://dx.doi.org/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](http://dx.doi.org/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](http://dx.doi.org/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](http://dx.doi.org/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](http://dx.doi.org/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](http://dx.doi.org/10.1145/800105.803397)

> **Comments:**
> **username_78**: Nice one.  Could you provide more links to the literature, on decidable cases etc. ?  
> **username_2**: @Sylvain: as is usual here, I have avoided linking directly to my own work but our TODS 2014 paper has all the key links.  
> **username_78**: Since I'm not bound by such usage habits, here is a link for others who might be interested: http://tods.acm.org/accepted/2013/SalamonClassification.pdf.  You could however provide a link to the PODS 1993 Chaudhuri & Vardi paper at http://dx.doi.org/10.1145/153850.153856 without being suspected of self-promotion.  

---

### Answer by username_79 on 2012-06-08. Score: 1

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

> **Comments:**
> **username_80**: Links or references, please. When you edit, would you consider make it standard fonts like everybody else?  
> **username_27**: Please use regular fonts. and run a spell checker  

---

### Answer by username_81 on 2020-02-10. Score: 1

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)***

> **Comments:**
> **username_81**: **Note:** Even $NPTIME$ has not been shown to be different from $DLOGSPACE$.  
> **username_81**: There also are related questions involving $CFL$ and $DCFL$ along with time and space complexity classes.  

---

### Answer by username_6 on 2024-06-26. Score: 0

Broadly what is the status of $GCD$, modular inverse and extended $GCD$?

Can we prove $GCD$ is not in $L$?


---

### Answer by username_82 on 2020-01-28. Score: 0

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

Recently, [Hugunin (2019)](https://link.springer.com/chapter/10.1007/978-3-030-17127-8_17) 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](https://ncatlab.org/homotopytypetheory/show/open+problems).


---

