Unsolved problems in computer science
Each problem comes from a named list, with the status its source gives it. Papex does not decide whether a problem is solved.
- Aanderaa–Karp–Rosenberg conjecture Open Must every deterministic algorithm for a non-trivial monotone graph property ask about every pair of vertices in the worst case?
- Average-case complexity of Shellsort Open What is the lowest possible average running time of Shellsort with a fixed sequence of gaps?
- Barendregt–Geuvers–Klop conjecture Open In a pure type system, if every term has some evaluation that terminates, must every evaluation terminate?
- BQP versus NP Open Can quantum computers solve NP-complete problems efficiently, and can they efficiently solve problems outside NP?
- Busy Beaver BB(2,5) Open What is the largest number of steps a halting 2-state, 5-symbol Turing machine can run, starting from a blank tape?
- Busy Beaver BB(3,3) Open What is the largest number of steps a halting 3-state, 3-symbol Turing machine can run, starting from a blank tape?
- Busy Beaver BB(6) Open What is the largest number of steps a halting 6-state, 2-symbol Turing machine can run, starting from a blank tape?
- Complexity of integer factorisation Open Can a classical computer find the prime factors of a large number in polynomial time?
- Complexity of matrix multiplication Open What is the fastest possible algorithm for multiplying two matrices?
- Complexity of the discrete logarithm Open Can a classical computer compute discrete logarithms in polynomial time?
- Complexity of the fast Fourier transform Open Can the discrete Fourier transform of n values be computed with asymptotically fewer than n log n arithmetic operations?
- Decidability of multiplicative-exponential linear logic Open Is there an algorithm that decides entailment in multiplicative-exponential linear logic (MELL)?
- Deterministic linear-time minimum spanning tree Open Can a minimum spanning tree be found deterministically in linear time by an algorithm that only compares edge weights?
- Dynamic optimality conjecture Open Do splay trees perform as well as any other binary search tree algorithm, up to a constant factor, on every sequence of accesses?
- Existence of one-way functions Open Do functions exist that are easy to compute but hard to invert?
- Exponential time hypothesis Claimed Does solving 3-SAT really require exponential time?
- Finding a simple closed quasigeodesic Open Can a simple closed quasigeodesic on a convex polyhedron be found in polynomial time?
- Generalised star-height problem Open Can every regular language be written as a regular expression with complement that nests Kleene stars at most one level deep?
- Graph canonisation versus graph isomorphism Open Is computing a canonical form of a graph no harder, up to polynomial time, than deciding whether two graphs are isomorphic?
- Graph isomorphism problem Open Can it be decided in polynomial time whether two graphs are the same up to relabelling?
- Hartmanis–Stearns conjecture Open If a machine can print the digits of a real number in real time, must that number be rational or transcendental?
- L versus NL Open Can every problem solvable by a nondeterministic machine with logarithmic memory also be solved deterministically with logarithmic memory?
- Log-rank conjecture Open Is the number of bits two parties must exchange to compute a Boolean function bounded by a polynomial in the logarithm of its matrix rank?
- NC versus P Open Can every problem solvable in polynomial time be solved in polylogarithmic time on a parallel computer with polynomially many processors?
- NP versus co-NP Open If a yes-answer to a problem can be checked quickly, can a no-answer always be checked quickly too?
- P versus BPP Open Can every problem that a randomised algorithm solves efficiently also be solved efficiently without randomness?
- P versus NP Open Can every problem whose answer is quick to check also be solved quickly?
- P versus PSPACE Open Can every problem that is solvable with a polynomial amount of memory also be solved in polynomial time?
- Recognising graphs of bounded clique-width Open For a fixed bound k, can it be decided in polynomial time whether a graph has clique-width at most k?
- Simultaneous embedding with fixed edges Open Can it be tested in polynomial time whether two graphs on the same vertices can be drawn together so that each is crossing-free and shared edges coincide?
- Skolem problem Open Is there an algorithm that decides whether a linear recurrence sequence, such as a Fibonacci-like sequence, ever reaches zero?
- Smallest and fastest median selection networks Open For each number of inputs n, how few comparators, and how few layers, can a comparator network have that always leaves the median of its n inputs on a fixed wire?
- Smallest and fastest sorting networks Open For each number of inputs n, how few comparators, and how few layers, can a comparator network have that sorts every input of n values?
- Solving parity games Open Can the winner of a parity game, played by moving a token on a coloured graph, be determined in polynomial time?
- Square-root sum problem Open Can a Turing machine decide in polynomial time whether a sum of square roots of integers is at most a given integer?
- Strongly polynomial linear programming Open Can linear programs be solved by an algorithm whose number of arithmetic steps depends only on the number of variables and constraints?
- Unique games conjecture Open Is approximating Unique Games NP-hard?
- X + Y sorting Open Can all pairwise sums of two lists of n numbers be sorted faster than the O(n² log n) time of ordinary sorting?
- Černý conjecture Open If a finite automaton with n states can be reset by some input word, is there always such a word of length at most (n − 1)²?