Related papers: Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

URL: http://arxiv.org/abs/2601.12621v1
Date: Sun, 18 Jan 2026 23:28:36 GMT
Title: Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
Authors: Radu Cosmin Dumitru, Ryo Yoshinaka, Ayumi Shinohara,
Abstract summary: We study the computational complexity of the case where the input sample is prefix-closed.<n>We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: It is well known that computing a minimum DFA consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the case where the input sample is prefix-closed. This formulation is equivalent to computing a minimum Moore machine consistent with observations along its runs. We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings. Furthermore, we show that the problem remains NP-hard as a decision problem even when the sample set consists of the prefixes of a single binary string. Our argument also extends to the corresponding problem for Mealy machines.

Related papers

Intermediate Results on the Complexity of STRIPS$_{1}^{1}$ [4.706932040794695]
It is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete.<n>We call a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.
arXiv Detail & Related papers (2026-02-09T14:21:10Z)
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
We show that Statistical Query hardness can be established when both the alphabet size and input length are in the number of states.<n>Our result is derived solely from the internal state-transition structure of semiautomata.
arXiv Detail & Related papers (2025-10-05T09:35:35Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
We focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Theta(n)$ queries to an NP oracle, quantumly $Theta(log n)$ queries suffice. Moving to approximate counting, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal.
arXiv Detail & Related papers (2024-01-08T14:59:48Z)
When Input Integers are Given in the Unary Numeral Representation [0.0]
Many NP-complete problems take integers as part of their input instances. The "unarization" of numbers has been known to bring a remarkably different effect onto the computational complexity of the problems. We present numerous NP-complete (or even NP-hard) problems, which turn out to be easily solvable when input integers are represented in unary.
arXiv Detail & Related papers (2023-12-07T15:09:24Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
arXiv Detail & Related papers (2023-06-28T16:33:39Z)
Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
We show that the hardness of SAT encodings for LEC instances can be estimated textitw.r.t some SAT partitioning. The paper proposes several methods for constructing partitionings, which, when used in practice, allow one to estimate the hardness of SAT encodings for LEC with good accuracy.
arXiv Detail & Related papers (2022-10-04T09:19:13Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z)
Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem [0.5584060970507505]
We design a derivation technique to tackle a few problems over maximal matchings in graphs. We get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the W -states as input. Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a 2-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings.
arXiv Detail & Related papers (2020-11-24T06:36:11Z)
Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
arXiv Detail & Related papers (2020-06-21T15:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.