論文の概要: On Theoretical Complexity and Boolean Satisfiability
- arxiv url: http://arxiv.org/abs/2112.11769v1
- Date: Wed, 22 Dec 2021 10:13:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-23 18:15:06.786754
- Title: On Theoretical Complexity and Boolean Satisfiability
- Title（参考訳）: 理論的複雑性とブール満足性について
- Authors: Mohamed Ghanem, Dauod Siniora
- Abstract要約: この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。
次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。
最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Theoretical complexity is a vital subfield of computer science that enables
us to mathematically investigate computation and answer many interesting
queries about the nature of computational problems. It provides theoretical
tools to assess time and space requirements of computations along with
assessing the difficultly of problems - classifying them accordingly. It also
garners at its core one of the most important problems in mathematics, namely,
the $\textbf{P vs. NP}$ millennium problem. In essence, this problem asks
whether solution and verification reside on two different levels of difficulty.
In this thesis, we introduce some of the most central concepts in the Theory of
Computing, giving an overview of how computation can be abstracted using Turing
machines. Further, we introduce the two most famous problem complexity classes
$\textbf{P}$ and $\textbf{NP}$ along with the relationship between them. In
addition, we explicate the concept of problem reduction and how it is an
essential tool for making hardness comparisons between different problems.
Later, we present the problem of Boolean Satisfiability (SAT) which lies at the
center of NP-complete problems. We then explore some of its tractable as well
as intractable variants such as Horn-SAT and 3-SAT, respectively. Last but not
least, we establish polynomial-time reductions from 3-SAT to some of the famous
NP-complete graph problems, namely, Clique Finding, Hamiltonian Cycle Finding,
and 3-Coloring.
- Abstract（参考訳）: 理論的複雑性は計算機科学の重要な分野であり、計算を数学的に調査し、計算問題の性質に関する多くの興味深い質問に答えることができる。
計算の時間と空間の要求を評価する理論的ツールと、問題の難易度を評価するツールを提供する。
また、数学において最も重要な問題、すなわち$\textbf{P vs. NP}$ millennium 問題の中核となる問題にも着目している。
本質的にこの問題は、ソリューションと検証が2つの異なる難易度レベルに存在するかどうかを問うものである。
本稿では,計算理論において最も中心的な概念をいくつか紹介し,チューリングマシンを用いた計算の抽象化について概説する。
さらに、最も有名な2つの問題複雑性クラスである$\textbf{p}$と$\textbf{np}$をそれらの関係とともに紹介する。
さらに,問題削減の概念と,異なる問題間の硬度比較を行うための重要なツールについて解説する。
その後、NP完全問題の中心に位置するブール満足度(SAT)の問題を示す。
次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。
最後に、3SATから有名なNP完全グラフ問題(Clique Finding, Hamiltonian Cycle Finding, 3-Coloring)への多項式時間短縮を確立する。
関連論文リスト
- Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。
本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
論文 参考訳（メタデータ） (2025-02-09T18:16:53Z) - 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) - When Input Integers are Given in the Unary Numeral Representation [0.0]
多くのNP完全問題は、入力インスタンスの一部として整数を取る。
数値の「統一」は、問題の計算複雑性に著しく異なる効果をもたらすことが知られている。
入力整数を単項で表すと容易に解けるNP完全問題(NP完全問題)が多数存在する。
論文 参考訳（メタデータ） (2023-12-07T15:09:24Z) - QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。
量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか?
QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文 参考訳（メタデータ） (2023-09-28T13:30:20Z) - Large Language Model for Science: A Study on P vs. NP [88.67249044141529]
大規模言語モデル(LLM)を用いて,P対NP問題の研究を促進・促進する。
具体的には、複雑な問題解決のためのLLMを用いた奥行き思考を促進する一般的なフレームワークであるソクラティック推論を提案する。
我々のP対NP問題に関するパイロット研究は、GPT-4が証明スキーマの生成に成功し、97の対話ターンを通して厳密な推論を行うことを示した。
論文 参考訳（メタデータ） (2023-09-11T17:49:27Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。
この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文 参考訳（メタデータ） (2023-06-07T12:19:22Z) - Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。
NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
論文 参考訳（メタデータ） (2023-05-26T05:31:25Z) - Quantum Programming of the Satisfiability Problem with Rydberg Atom
Graphs [1.2179548969182574]
実験では、リドベルク原子を用いて(すなわち、満足度(3-SAT)の問題をプログラムし、解を求める)。
論文 参考訳（メタデータ） (2023-02-28T07:49:10Z) - Exceeding Computational Complexity Trial-and-Error Dynamic Action and
Intelligence [0.0]
計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。
本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。
また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
論文 参考訳（メタデータ） (2022-12-22T21:23:27Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。