論文の概要: Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

• arxiv url: http://arxiv.org/abs/2601.12621v1
• Date: Sun, 18 Jan 2026 23:28:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.706051
• Title: Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
• Title（参考訳）: 単一文字列のプレフィックスから決定論的有限状態マシンを学習するNP-Complete
• Authors: Radu Cosmin Dumitru, Ryo Yoshinaka, Ayumi Shinohara,
• Abstract要約: 入力サンプルがプレフィックスクローズされた場合の計算複雑性について検討した。 サンプル集合がバイナリ文字列のすべてのプレフィックスで構成されている場合,問題はNPハードで近似可能であることを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 最小の DFA を与えられた正および負の例の集合と整合する計算がNPハードであることはよく知られている。 従来の研究では、問題の引き抜きが難しい、あるいは困難な状態にある入力サンプルの条件が特定されていた。 本稿では,入力サンプルがプレフィックスクローズされた場合の計算複雑性について検討する。 この定式化は、最小のムーアマシンをその走行中の観測と整合する計算と等価である。 サンプル集合がバイナリ文字列のすべてのプレフィックスで構成されている場合,問題はNPハードで近似可能であることを示す。 さらに、サンプル集合が1つのバイナリ文字列のプレフィックスで構成されている場合でも、その問題は決定問題としてNPハードのままであることを示す。 我々の議論は、Mealyマシンの対応する問題にも及んでいる。

関連論文リスト

• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
  我々は,アルファベットサイズと入力長の両方が状態数である場合に,統計的クエリの硬さを確立することができることを示す。 この結果は、半オートマタの内部状態遷移構造からのみ導かれる。
  論文  参考訳（メタデータ） (2025-10-05T09:35:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
  本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。 まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。 近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
  論文  参考訳（メタデータ） (2024-01-08T14:59:48Z)
• When Input Integers are Given in the Unary Numeral Representation [0.0]
  多くのNP完全問題は、入力インスタンスの一部として整数を取る。 数値の「統一」は、問題の計算複雑性に著しく異なる効果をもたらすことが知られている。 入力整数を単項で表すと容易に解けるNP完全問題(NP完全問題)が多数存在する。
  論文  参考訳（メタデータ） (2023-12-07T15:09:24Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem [0.5584060970507505]
  グラフの最大マッチングに関するいくつかの問題に対処するための導出手法を設計する。 入力として空の状態が与えられたとき、可能なすべてのマッチングに対する重ね合わせと、入力としてW-状態が与えられたとき、すべての最大マッチングに対する重ね合わせを得る。 本研究の主な成果は,QAOA+アルゴリズムの2正規グラフ上での実行時の出力状態に対応するマッチングの期待サイズが,全てのマッチングの均一分布から得られるマッチングサイズよりも大きいことである。
  論文  参考訳（メタデータ） (2020-11-24T06:36:11Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。