388 problems
Exponential Time Hypothesis. There is no -time algorithm which can determine whether a given 3SAT formula on variables is satisfiable.
For each integer n=2, let CDFT(n) be the minimum number of steps needed to compute every output of the unnormalized complex DFT yj=sum(l=0)^(n-1) exp(-2piijl/n)xl, 0<=j<n. Initiall…
For every integer k = 1 and every metric space, prove that there is a deterministic online k-server algorithm whose movement cost on every request sequence is at most k times the o…
Conjecture. . Equivalently, for every there is a constant such that for every some arithmetic program multiplies compl…
Hendrych's NP-hardness conjecture. The Bayesian AOD problem is NP-hard. This conjecture is resolved in the source: the paper proves NP-hardness for its regularized A-optimal design…
The Fooling-Set-Submatrix problem takes integers and an -matrix as input, and asks whether contains a fooling-set submatrix of size . NP-hardness…
Let be positive integers with and , and let and . Let be a family of graphs for which recognizing generating subgraphs isomorphic…
For every fixed finite set of forbidden permutation patterns, does there exist an algorithm that, given a -avoiding permutation and an integer , enumerat…
For all positive integers and all total Boolean functions and , define…
Given a finite pure -dimensional simplicial complex , decide whether its face poset can be partitioned into Boolean intervals of the form…
For every integer and every graph family such that for every , define to be the maximum n…
Given a finite graph , decide whether every minimal separator of is bisimplicial, that is, whether for every set such that there exist distinct vertice…
Let be a fixed graph with , and let be a fixed nonempty family of graphs. If no graph is a subgraph of any blow-up of , then for ever…
For a fixed integer , given a planar graph , decide whether there exists a family of pairwise interiorly disjoint, non-self-intersecting grid paths s…
For every fixed integer and every constant , let be a random -uniform hypergraph on vertices in which each -element hyperedge is present independen…
Given a finite poset of height at most , consider the normal-play poset game in which a move selects an element and removes together with every remaining el…
Given an approval profile and a target committee size , determine whether there exists a polynomial-time algorithm that outputs a committee of size satisfying both j…
Let be a set of instances equipped with an unknown total order , and let be the class of threshold concepts whose positive sets are prefixes of…
Given a finite simple unweighted graph , decide whether the standard Goemans–Williamson semidefinite relaxation of Max-Cut has the same optimal value as the integer Max-Cu…
Determine whether the unique solution of every linear complementarity problem with a rational P-matrix and rational right-hand side can be computed in time polynomial in the bit le…
Given a weighted graph , where , find an integral cycle basis minimizing its total weight…
Conjecture: For every quantum polynomial-time sampler and every classical string that outputs with probability , there is a quantum program for of length at…
This entry tracks UIR3 computational-complexity problem. It closes the gap between the known polynomial height-two case and PSPACE-complete height-four case. Latest development A r…
Determine whether there exists a purely combinatorial algorithm for boolean matrix multiplication running in time O(n^{2+o(1)}) without using algebraic Strassen-like tensor methods…
Determine whether Condon's simple stochastic games can be solved in polynomial time: given a two-player zero-sum turn-based stochastic game with binary decisions, rational transiti…