2025-05-16 | | Total: 6
The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for $\Sigma^P_2$- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a $\Sigma^P_2$-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.
Canonical polyadic decomposition (CPD) is at the core of fast matrix multiplication, a computational problem with widespread implications across several seemingly unrelated problems in computer science. Much recent progress in this field has used randomized heuristic search to find new CPDs, often over a finite field. However, if these techniques fail to find a CPD with low enough rank, they cannot prove that no such CPD exists. Consequently, these methods fail to resolve certain long-standing questions, such as whether the tensor corresponding to $3\times 3$ matrix multiplication has rank less than 23. To make progress on these problems, we develop a novel algorithm that preserves exactness, i.e. they can provably verify whether or not a given tensor has a specified rank. Compared to brute force, when searching for a rank-$R$ CPD of a $n_0\times\dots\times n_{D-1}$-shaped tensor over a finite field $\mathbb{F}$, where $n_0\ge \dots\ge n_{D-1}$, our algorithm saves a multiplicative factor of roughly $|\mathbb{F}|^{R(n_0-1)+n_0(\sum_{d\ge 1} n_d)}$. Additionally, our algorithm runs in polynomial time. We also find a novel algorithm to search border CPDs, a variant of CPDs that is also important in fast matrix multiplication. Finally, we study the maximum rank problem and give new upper and lower bounds, both for families of tensor shapes and specific shapes. Although our CPD search algorithms are still too slow to resolve the rank of $3\times 3$ matrix multiplication, we are able to utilize them in this problem by adding extra search pruners that do not affect exactness or increase asymptotic running time.
The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of quantum algorithms for simulating such geometrically local systems. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that quantum algorithms for short-time dynamics have the same computational complexity as polynomial-time probabilistic classical computation. Third, we show that the computational complexity of quantum algorithms for long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.
The multi-agent path finding (MAPF) problem asks to find a set of paths on a graph such that when synchronously following these paths the agents never encounter a conflict. In the most widespread MAPF formulation, the so-called Classical MAPF, the agents sizes are neglected and two types of conflicts are considered: occupying the same vertex or using the same edge at the same time step. Meanwhile in numerous practical applications, e.g. in robotics, taking into account the agents' sizes is vital to ensure that the MAPF solutions can be safely executed. Introducing large agents yields an additional type of conflict arising when one agent follows an edge and its body overlaps with the body of another agent that is actually not using this same edge (e.g. staying still at some distinct vertex of the graph). Until now it was not clear how harder the problem gets when such conflicts are to be considered while planning. Specifically, it was known that Classical MAPF problem on an undirected graph can be solved in polynomial time, however no complete polynomial-time algorithm was presented to solve MAPF with large agents. In this paper we, for the first time, establish that the latter problem is NP-hard and, thus, if P!=NP no polynomial algorithm for it can, unfortunately, be presented. Our proof is based on the prevalent in the field technique of reducing the seminal 3SAT problem (which is known to be an NP-complete problem) to the problem at hand. In particular, for an arbitrary 3SAT formula we procedurally construct a dedicated graph with specific start and goal vertices and show that the given 3SAT formula is satisfiable iff the corresponding path finding instance has a solution.
A superpermutation is a sequence that contains every permutation of $n$ distinct symbols as a contiguous substring. For instance, a valid example for three symbols is a sequence that contains all six permutations. This paper introduces a new algorithm that constructs such sequences more efficiently than existing recursive and graph-theoretic methods. Unlike traditional techniques that suffer from scalability and factorial memory demands, the proposed approach builds superpermutations directly and compactly. This improves memory usage, enabling the construction of larger sequences previously considered impractical.
Resource allocation problems in which demand is splittable are usually solved using different solution methods from their unsplittable equivalents. Although splittable problem instances can be the easier of the two (for example, they might simply correspond to a linear relaxation of a discrete problem), there exist many problems, including routing problems, for which the converse is true. That is, the technology for solving unsplittable problems is mature, but the splittable counterpart is not. For such problems, one strategy that has recently shown potential is the use of an a priori splitting rule in which each customer's demand is split into smaller pieces in advance, which enables one to simply solve the splittable problem as an instance of the unsplittable version. An important factor to consider is the number of pieces that result after this splitting. A large numbers of pieces will allow more splitting patterns to be realizable, but will result in a larger problem instance. In this paper, we introduce a splitting rule that minimizes the number of pieces, subject to the constraint that all demand splitting patterns remain feasible. Computational experiments on benchmark instances for the vehicle routing problem and a time-windows extension show that the solution quality of our proposed splitting rule can match the performance of existing approaches.