Wikipedia only lists two problems under "unsolved problems in computer science":
What are other major problems that should be added to this list?
Rules:
- Only one problem per answer
- Provide a brief description and any relevant links
61 Answers
$\begingroup$
$\endgroup$
8
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. A nice overview of the state of the art is Sara Robinson, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38(9), 2005.
Update: Andrew Stothers (in his 2010 thesis) showed that $\omega < 2.3737$, which was improved by Virginia Vassilevska Williams (in a July 2014 preprint) 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).
Update (Nov 4, 2023): "New Bounds for Matrix Multiplication: from Alpha to Omega" proved that $\omega \leq 2.371552$.
-
$\begingroup$ 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)$. $\endgroup$– MitchCommented Sep 13, 2010 at 17:16
-
$\begingroup$ 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! $\endgroup$ Commented Sep 13, 2010 at 17:39
-
14$\begingroup$ 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. $\endgroup$– ZeyuCommented Nov 13, 2010 at 2:39
-
3$\begingroup$ 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})$ $\endgroup$ Commented Dec 8, 2011 at 22:27
-
1$\begingroup$ 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. $\endgroup$ Commented Jan 31, 2014 at 17:35
$\begingroup$
$\endgroup$
4
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.
Determining whether two graphs are isomorphic can usually be done quickly, for instance by software such as nauty and saucy. On the other hand, Miyazaki constructed classes of instances 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, 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?, IPL 25, 127–132, 1987)
Shiva Kintali has a nice discussion of the complexity of GI at his blog.
Laszlo Babai proved that Graph Isomorphism is in quasipolynomial time.
-
-
$\begingroup$ I cranked an exact lower bound for generic brute force automorphism detection. 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. $\endgroup$ Commented Jan 31, 2014 at 17:25
-
1$\begingroup$ Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$– RaphaelCommented Jan 4, 2017 at 21:56
-
7$\begingroup$ The claim was restored : people.cs.uchicago.edu/~laci/update.html $\endgroup$– nitingCommented Jul 7, 2017 at 17:34
1
-
$\begingroup$ 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 ... $\endgroup$ Commented Jan 31, 2014 at 17:45
3
-
2$\begingroup$ This answer should be made CW now too... $\endgroup$– ShaneCommented Aug 17, 2010 at 17:38
-
2$\begingroup$ and related questions like is NP = MA = AM? $\endgroup$ Commented Aug 18, 2010 at 5:08
-
1$\begingroup$ See the closely related question cstheory.stackexchange.com/questions/64/… $\endgroup$ Commented Aug 19, 2010 at 1:54
$\begingroup$
$\endgroup$
3
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?
-
11$\begingroup$ I'll add to this question: would showing the nonexistence of strongly polynomial LP imply any class separation results? $\endgroup$ Commented Aug 27, 2010 at 23:59
-
$\begingroup$ ,,,and the Hirsch conjecture... $\endgroup$ Commented Nov 10, 2011 at 4:27
-
8$\begingroup$ 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 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). $\endgroup$ Commented Jan 30, 2012 at 16:11
$\begingroup$
$\endgroup$
5
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?, JCSS 63, 512–530, 2001.
ETH is widely believed, but likely to be difficult to prove, as it implies many other complexity class separations.
-
4$\begingroup$ 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. $\endgroup$– HolgerCommented Aug 23, 2010 at 9:16
-
18$\begingroup$ No? IMHO, your argument implies that ETH is even more of a major open problem than PvsNP. $\endgroup$– JeffεCommented Aug 24, 2010 at 6:05
-
$\begingroup$ Could you explain why $P \ne NP$ does not imply the ETH? $\endgroup$– EmilCommented Aug 31, 2010 at 12:23
-
13$\begingroup$ If $NP = PTIME(n^{\log n})$, then $P\ne NP$, but ETH is false. $\endgroup$– JeffεCommented Aug 31, 2010 at 15:30
-
4$\begingroup$ Ah ok. But you mean DTIME($n^{\log n}$)? $\endgroup$– EmilCommented Sep 1, 2010 at 14:03
$\begingroup$
$\endgroup$
2
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:
- any syntactically correct program models a polynomial-time computable graph problem and
- 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 for an informal discussion and M. Grohe: The Quest for a Logic Capturing PTIME (LICS 2008) for a more technical survey.
-
3$\begingroup$ 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. $\endgroup$ Commented Aug 18, 2010 at 12:26
-
5$\begingroup$ 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: rjlipton.wordpress.com/2010/04/05/… $\endgroup$– HolgerCommented Aug 18, 2010 at 16:25
$\begingroup$
$\endgroup$
5
Permanent versus 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.
-
7$\begingroup$ 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. $\endgroup$ Commented Dec 9, 2011 at 0:59
-
-
11$\begingroup$ @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) $\endgroup$ Commented Mar 2, 2012 at 17:38
-
$\begingroup$ 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. $\endgroup$ Commented Jan 31, 2014 at 18:10
-
$\begingroup$ @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, citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.116 $\endgroup$ Commented Feb 5, 2015 at 7:22
$\begingroup$
$\endgroup$
4
Is the unique games conjecture true?
And: Given that there are sub-exponential time approximation algorithms for Unique Games, where does the problem ultimately rest in terms of the complexity landscape?
-
$\begingroup$ 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? $\endgroup$ Commented Aug 17, 2010 at 17:55
-
$\begingroup$ 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? $\endgroup$ Commented Aug 17, 2010 at 18:58
-
2$\begingroup$ In retrospect, I thought I should include a pointer toward this pre-print. In my opinion, it's as big of a development as the paper I have linked in the answer. $\endgroup$ Commented Aug 31, 2010 at 11:09
-
2$\begingroup$ 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. $\endgroup$ Commented Jan 6, 2017 at 21:28
$\begingroup$
$\endgroup$
2
The dynamic optimality conjecture for splay trees.
Or more generally: Is any online dynamic binary search tree O(1)-competitive?
-
-
$\begingroup$ There are also the more recent zipper trees, which are O(lg lg n) competitive without giving up O(lg n) worst-case access time. $\endgroup$– jbappleCommented Oct 16, 2010 at 14:03
$\begingroup$
$\endgroup$
0
A linear time deterministic algorithm for the minimum spanning tree problem.
$\begingroup$
$\endgroup$
1
Can we compute the 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) 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
-
5$\begingroup$ 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: arxiv.org/abs/1201.2501v1 $\endgroup$– ShadokCommented Feb 2, 2012 at 16:20
$\begingroup$
$\endgroup$
1
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.
-
7$\begingroup$ This is also related to propositional proof complexity. There is a polynomial propositional proof system iff $NP$ is equal to $coNP$. $\endgroup$– KavehCommented Aug 17, 2010 at 22:01
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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.
-
16$\begingroup$ 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 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. $\endgroup$ Commented Aug 24, 2010 at 6:33
$\begingroup$
$\endgroup$
2
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$ ?
-
8$\begingroup$ 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.) $\endgroup$ Commented Sep 11, 2010 at 12:00
-
7$\begingroup$ Update (STOC 2015): Backurs and Indyk give evidence that better-than-quadratic time is not possible. See rjlipton.wordpress.com/2015/06/01/puzzling-evidence . $\endgroup$ Commented Oct 11, 2015 at 1:36
$\begingroup$
$\endgroup$
8
Are there truly subquadratic-time algorithms (meaning $O(n^{2-\delta})$ time for some constant $\delta>0$) for 3SUM-hard Problems?
In 2014, Grønlund and Pettie 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.
-
9$\begingroup$ 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.. $\endgroup$– PiotrCommented Aug 25, 2010 at 19:36
-
3$\begingroup$ 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. $\endgroup$ Commented Aug 25, 2010 at 20:34
-
1$\begingroup$ I was under the impression that we do not have n^2 lower bound for any problem in NP. $\endgroup$ Commented Nov 10, 2011 at 4:40
-
1$\begingroup$ 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. $\endgroup$ Commented Dec 1, 2012 at 5:42
-
5$\begingroup$ A recent arXiv paper claims to have settled this conjecture by giving sub-quadratic algorithms for 3-SUM. $\endgroup$– MangaraCommented Jul 7, 2014 at 17:33
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
7
- Isomorphism Conjecture. (Are all NP-complete problems the "same" problem?)
- Can cryptography be based upon an NP-complete problem?
- What is the size of NP within EXP?
and, a little further away from the mainstream:
(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.)
-
$\begingroup$ Is this the same as p-measure in the Complexity Zoo? Where would I go to read more about it? $\endgroup$ Commented Aug 17, 2010 at 17:48
-
2$\begingroup$ 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). cs.iastate.edu/~lutz/=PAPERS/qset.ps (in postscript, I hope that's ok) $\endgroup$ Commented Aug 17, 2010 at 18:02
-
$\begingroup$ Thanks. Here is a PDF of that paper for those who can't read PS: archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/… $\endgroup$ Commented Aug 17, 2010 at 23:17
-
2$\begingroup$ 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. $\endgroup$ Commented Aug 18, 2010 at 2:24
-
1$\begingroup$ @Artem: you could start here: blog.computationalcomplexity.org/2003/03/… $\endgroup$ Commented Aug 16, 2011 at 11:15
$\begingroup$
$\endgroup$
4
What is the approximability of Metric TSP? 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]). 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] [Good version]).
The upper bound on approximability was recently lowered to $13/9$ (Mucha 2011 "13/9 -approximation for Graphic TSP" [PDF])
-
2$\begingroup$ Metric TSP recently done by 3/2 - e where e is constant (near 0.002) $\endgroup$– SaeedCommented Jun 2, 2011 at 18:34
-
2$\begingroup$ some discussion of metric TSP on Godel's lost letter $\endgroup$ Commented Jan 26, 2012 at 23:42
-
2$\begingroup$ @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. $\endgroup$ Commented May 17, 2012 at 11:50
-
$\begingroup$ @AlexGolovnev, Hi Alex, Yes, but my comment was before the new paper coming ;) (I saw Oveis Gharan paper at that time). $\endgroup$– SaeedCommented May 17, 2012 at 19:51
$\begingroup$
$\endgroup$
7
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.
-
11$\begingroup$ 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. $\endgroup$ Commented Sep 13, 2010 at 17:12
-
1$\begingroup$ 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. $\endgroup$– MarcCommented Sep 14, 2010 at 12:05
-
$\begingroup$ Is there a good exposition on Shannon's work? $\endgroup$– TurboCommented Nov 15, 2010 at 23:22
-
3$\begingroup$ The argument is detailed in the following lecture notes: math.tau.ac.il/~zwick/scribe-boolean.html $\endgroup$– MarcCommented Nov 16, 2010 at 19:19
-
$\begingroup$ This is an excellent problems and brings back fond memories of being assigned Shanon's result my second year of university. $\endgroup$ Commented Jan 6, 2017 at 21:31
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Separate NEXP from BPP. People tend to believe BPP=P, but no one can separate NEXP from BPP.
$\begingroup$
$\endgroup$
Derandomization of the Polynomial Identity Testing problem
The problem is the following: Given an arithmetic circuit 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$.
$\begingroup$
$\endgroup$
2
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 and Cramer-Shoup.
-
3$\begingroup$ Well, we do know DLP is contained within BQP. $\endgroup$ Commented Sep 5, 2010 at 13:28
-
$\begingroup$ DLP was recently put in quasi-P for the group $G = \mathbb{F}_{p^n}^\times$ $\endgroup$ Commented Aug 28, 2019 at 5:05
$\begingroup$
$\endgroup$
1
I know the OP asked for only one problem per post, but the RTA (Rewriting Techniques and their Applications) 1 and TLCA (Typed Lambda Calculi and their Applications) conferences both maintain lists of open problems in their fields 2. These lists are quite useful, as they also include pointers to previous work done on attempting to solve these problems.
-
1$\begingroup$ No problem. Does anybody know of any other similar lists from other conferences? They're quite interesting to read. $\endgroup$ Commented Aug 25, 2010 at 20:57
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
8
Is there a Quantum PCP theorem?
-
$\begingroup$ This question was mentioned on Scott Aaronson's blog a while ago scottaaronson.com/blog/?p=139 but I don't know if there has been any progress since. $\endgroup$ Commented Aug 18, 2010 at 11:35
-
$\begingroup$ I think this answer needs to be updated. $\endgroup$– KavehCommented Jun 25, 2015 at 22:55
-
$\begingroup$ @Kaveh: What would you like to see added? $\endgroup$ Commented Jun 26, 2015 at 1:17
-
-
$\begingroup$
$\endgroup$
1
There are a lot of open problems in lambda calculi (typed and untyped). See the TLCA list of open problems for details; there is also a nice PDF version without the frames.
I particularly like problem #5:
Are there terms untypable in $F_ω$ but typable with help of positive recursive types?
-
3$\begingroup$ Thanks to Dominic Mulligan for pointing me to this particular list of problems. $\endgroup$ Commented Aug 30, 2010 at 21:20
$\begingroup$
$\endgroup$
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?)