NP完全

このタグでブログを書く

言葉の解説

ネットで話題

NP完全

(サイエンス)

【えぬぴーかんぜん】

NP Complete.
言語のクラス. または問題の性質. 言語以外に問題についても同様に定義できる.
ある言語Lが $L \in \mathrm{NP}$ であり, かつ, 任意のNP言語がその言語に帰着されるならば, その言語はNP完全であるという.
→http://qwiki.caltech.edu/wiki/Complexity_Zoo#npc

リスト::数学関連

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

情報系学生のお勉強覚書•1年前

『COMPUTERS AND INTRACTABILITY』を読んで生まれた疑問を解決する

久しぶりに更新します。最近『Computers and Intractability』という、NP完全問題に関する本を読んでいました。 www.amazon.co.jp いくつか分からない単語とかがあり、それらを一応？解決したので覚書として記録します。多項式階層以下が分からなかった感じですが、復習としてクラスPやNP、NP完全についても触れておきます。クラスP クラスNP NP完全多項式階層 NP-easy 疑似多項式時間アルゴリズム強力なNP完全性クラスP 決定性Turing機械で、多項式時間で解ける(yesかnoかの判別がつく)問題のクラス。計算量の関数yが、入力xに関して、y…

#理論計算幾何学#NP完全#NP-easy

ネットで話題

375ブックマーク CiNii - ぷよぷよはNP完全 JaLC IRDB Crossref DataCite NDL NDL-Digital RUDA JDCat NINJAL CiNii Articles CiNii Books CiNii Dissertations DBpedia Nikkei BP KAKEN Integbio MDR PubMed LSDB Archive 公共データカタログムーンショット型研究開発事業

cir.nii.ac.jp

55ブックマーク初心者が学ぶP,NP,NP困難(Hard),NP完全(Complete)とは（わかりやすく解説） - MotoJapan's Tech-Memo

motojapan.hateblo.jp

45ブックマーク NP完全問題 - Wikipedia NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合...

ja.wikipedia.org

40ブックマーク PとNPとNP完全とNP困難 - 大人になってからの再学習

zellij.hatenablog.com

29ブックマーク一般化ぷよぷよの NP 完全性

www.kurims.kyoto-u.ac.jp

13ブックマーク Kyoto University Research Information Repository: 一般化ぷよぷよのNP完全性 (計算機科学基礎理論とその応用)ダウンロード数: 8768 このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/2433/47272

repository.kulib.kyoto-u.ac.jp

13ブックマーク NP完全とかNP困難とか - nsasakiの勉強メモ

nsasaki.hatenadiary.org

11ブックマークブロゴスフィアで起こる「批判」の応酬を鎮めようとすればNP完全問題にぶつかるかもしれない: DESIGN IT! w/LOVE 不確実な時代をクネクネ蛇行しながら道を切りひらく非線形型ブログ。人間の思考の形の変遷を探求することをライフワークに。ジョージ・ジョンソンの『量子コンピュータとは何か』という本を紹介した際に、核爆発のシミュレーション実験を行うための計算は、現存する中で最速の部類にはいるスーパーコンピュータを用いて...

gitanez.seesaa.net

11ブックマーク一般化ぷよぷよのNP完全性 (計算機科学基礎理論とその応用) ：PDF

repository.kulib.kyoto-u.ac.jp

関連ブログ

医療～數論-未解決問題を証明!蓑輪博之•6日前

総目次：蓑輪博之

Bing Image Creatorによって作成：蓑輪博之數学フェルマーの最終定理の初等的証明 4色定理の証明線分演算 π～eの無理性・超越性コラッッ予想の証明 ABC予想の証明ゴールドバッハ予想の証明ルジャンドル予想の証明双子素數予想の証明奇数の完全數は存在為ない証明友愛數の偶然及び婚約數の奇跡ブロカールの問題の証明時空を超えた生命の確率五次方程式に解の公式が存在為ない証明初等數学を俯瞰為る工学電気・電子工学フーリエ解析～信号処理ラプラㇲ変換～制御工学電気・電子回路電気機械-変圧器・回転機包絡線ダイオード検波器の解析・位相変調コンピュータ～社会自動…

医療～數論-未解決問題を証明!蓑輪博之•6日前

ミレニアム懸賞問題③：P≠NP予想の証明：蓑輪博之

はじめにゲームに有用な數学-計算量及び複雑性・テンソル・群論ゲーム木の複雑度決定問題及び最適化問題 NP困難 NP完全 PSPACE 純碁の計算複雑性理論 5路盤や6路盤では、純碁はPに属為る。 7路盤や8路盤では、純碁の計算複雑性は未解決である。 9路盤では、純碁はPSPACE完全である。トランプのポーカールービックキューブ 2×2×2は、最適解が11手以内である。 3×3×3は、最適解が20手以内である。 4×4×4は、最適解が29手以内である。 5×5×5は、最適解の上界は未蜘である。テンソル計算量や複雑さを計算為る方法テンソルの特殊な例群論ルービックキューブ群 P≠…

eijirouの競プロ参加記•1ヶ月前

AHC025 参加記

公式ビジュアライザ（seed = 5） AHC025で優勝しました。長期AHCの過去最高順位は10位だったということもあり、非常に嬉しく思います。順位表はじめに解法だけでなく、考察や余談についても記載しました。重要度が低いと思われるものは折りたたみにしました。必要に応じてクリック（タップ）してください。ベイズ推定やMCMCについては私自身が詳しくないため、コンテスト後に少し勉強して理解したことを書きました。「お気持ち」だけ汲み取っていただければ幸いです。アイテム集合に対して、それらの重さ（の推定値）の和をと表記しました。行儀が悪い表現ですがお許しください。環境によっては数式が…

amamanamam•2ヶ月前

トランザクションの同時実行（静的アプローチ）

この記事は「リレーショナルデータベース入門第３版」のトランザクションの同時実行の章の一部のサーベイです。はてなのtex記法が上手くいかないので、定義の部分は別でtexで書いたもののキャプチャを貼るという暴挙に出ていますトランザクションの同時実行とスケジュールトランザクション集合{T1,...,Tn}が与えられた時、ある時刻t1にはTiの第 j ステップを次の時刻t2ではTkの第 l ステップを ( iとkは必ずしも異なる必要性はない) 次の時刻t3ではTiの第 j+1 ステップをという具合に複数のトランザクション実行していくことをトランザクションの同時実行という。定義(スケジュ…

ふかだの編入体験記•3ヶ月前

令和6年度大阪大学基礎工学部編入体験記

はじめにはじめまして．ふかだ（@towardbluesky）と申します． 2023年7月8日と9日に実施された編入試験で大阪大学基礎工学部情報科学科ソフトウェア科学コースに合格したので，体験記を書きます！はじめに自己紹介勉強内容英語（TOEIC）数学物理過去問面接・口頭試問出願情報試験の内容英語（TOIEC）数学（120分）物理（90分）面接・口頭試問どうして合格できたのか伝えたいこと余談自己紹介名前：ふかだ出身：N高専情報科席次：1年生1位，2年生2位，3年生1位，4年生1位受験年度：2024年度（令和6年度）併願校：広島大学情報科学部，京…

古い土地•4ヶ月前

可積分系の歴史：完全に解くことの系譜

私は論文 [6] を書いた後，この分野を離れました．お話ししたことはそこまでの歴史です．そしてその後もたくさんの歴史がありました．大変面白いことがたくさん起こりまして，それは東京で開かれた会議で見ることができました．しかし，あれは本当にエキサイティングな時期だった．毎日研究室に入ると，何かしら新しいことが起こったものです．本当に，本当にエキサイティングな時期だった．そして残念なことに，私はあの興奮を 2 度と再現することはできませんでした．御来聴いただき，ありがとうございました．（ロバート・ミウラ／著、梶原健司・及川正行／訳『ソリトンと逆散乱法：歴史的視点から』） wagaizumo.hat…

STORES Product Blog•4ヶ月前

正規表現のPrettier、パーサに取り組むために読んだ本、RubyKaigi 2023で面白かった発表。深掘りRubyKaigi 2023 with spikeolaf & makenowjust 文字起こしレポート vol.3

2023年6月15日に『深掘りRubyKaigi 2023 with spikeolaf & makenowjust』を開催しました。イベントの内容をほぼ全文文字起こし形式でお届けします。この記事は第3部です。 hey.connpass.com 登場人物ゲスト makenowjust/藤浪大弥さん spikeolaf/金子雄一郎さん STORES fujimura/藤村大介 shyouhei/卜部昌平 hogelog/小室直 LramaとRaccの関係性 fujimura：ここからは質疑応答コーナーに入りますので、みなさん質問があればどしどしZoomもしくはTwitterにお寄せい…

niwatakoのはてなブログ•5ヶ月前

2023/05 のarXiv ブロックチェーン関連新着論文概要 DeepL翻訳

arXivで「Blockchain」で検索した新着論文の概要をDeepLで翻訳しています。帯域外談合でブロックチェーンの合理性を壊す Published at 2023/05/01 04:10:08 (JST) Breaking Blockchain Rationality with Out-of-Band Collusion ブロックチェーンシステムは、その安全性のために合理性の仮定に頼ることが多く、ノードが利益を最大化するように動機づけられることを期待しています。このため、これらのシステムは、ノードが正直なプロトコルを実行するようインセンティブを与えるようにプロトコルを設計しますが、帯域…

脛孝行のすねかじり日記•6ヶ月前

「考えない」は過小評価されている

「考えすぎない方がいいよ」よく言われる言葉だ。「思考停止をするな」これもよく言われる言葉だ。もちろん時と場合によって、考えた方がいいのか考えない方がいいのかは変わるだろう。だが、一般的に、例えば考えても考えなくても今すぐ何かが変わるという場合でないときに、よく考えたほうがいいのか、考えすぎないほうがいいのか？さて、昨今は何でも深く考えることがよしとされ、「思考停止」という言葉がレッテルとして貼り付けられまくっているように感じる。だが、待ってほしい。考えないことは悪なのか？むしろ私は、今すぐ考える必要がないことは考えなくていいと思っている。自分はよく考えたくなってしまうけど、途中で考えた…

あめんばーどのバーチャル日記•6ヶ月前

【競プロ】作問振り返りメモ

無事コンテストが終わることができて良かったですが、その上で反省点も非常に多い作問でした。思い出としての振り返りもいっぱいあるんですが、それは別の記事にすることにして当記事につきましては作問にあたっての反省点や留意点をまとめていけたらと思います。反省と言う割には、結構文章は適当です。苦手なので。どちらかというと自分のメモ向きに書いたので、他人に見せる感じではありません。ご了承ください。

PyDocument•7ヶ月前

巡回セールスマン問題の基礎：概念と解決方法

巡回セールスマン問題（TSP）は、組合せ最適化問題の一種であり、与えられた複数の都市とそれらをつなぐ距離のデータをもとに、全ての都市をちょうど1度ずつ訪問し、最短の距離を旅する経路を求める問題です。TSPは、最適な解を求めることがNP困難であるため、実用的な問題においては、大規模な都市の組み合わせの場合には、近似解法が一般的に使用されます。以下では、TSPの基本的な概念といくつかの解決方法について説明します。 NP困難とは、計算量理論において、NP完全問題と同じ程度に難しいと考えられている問題のことです。NP完全問題とは、非決定性チューリングマシンで多項式時間で解ける問題のうち、どのNP問題で…

shakayamiの日記•8ヶ月前

人の最大の力を競う数学の大会

mathcompetition2020.com 人の最大の力を競う数学の大会、優勝してしまった… — しゃかやみ (@shakayami_) 2023年3月11日 pic.twitter.com/wGaYJ8cm7z — しゃかやみ (@shakayami_) 2023年4月1日匿名希望になってもうた pic.twitter.com/PKCkL70Gbe — しゃかやみ (@shakayami_) 2023年4月1日匿名希望はわたしです問題 drive.google.com 問1 (i)これはO(HW)のdp 実は斜め移動の回数を固定すると縦・横の移動係数も定まるので多項係数となる。結局…

akon2.00βのよっぱらいの戯言•8ヶ月前

計算量複雑性(computational complexity)

理論的には解けるが現実的な時間では解けない問題 https://motojapan.hateblo.jp/entry/2017/11/15/082738https://daigakudenki.com/np-hard/ https://tinyurl.com/2hq7ogtb 量子コンピュータで効率良く解くことができる問題のクラスは BQP (bounded-error, quantum, polynomial time)と呼ばれていて、因数分解などが含まれている。クラス BQP にクラス P が含まれることは明らかだが、NP完全問題はクラス BQP に含まれないと予想されている（証明された…

El librero la Fontana・ホンタナ氏の本棚•9ヶ月前

ベッドルームで群論を

グルーブ感のある科学エッセイベッドルームで群論を――数学的思考の愉しみ方作者:ブライアン・ヘイズみすず書房 Amazon よくジャズの曲や演奏で「グルーブ・Groove感」という言い方をするがそれっていったい何だろう？と思っていた。グルーブについてBRUTUSの山下達郎のインタビューの中に書かれていて、曰く、その楽曲の作り出す世界観の中に（言わばマイクロコスモス：小宇宙の中に）入っていく感じ。自分が楽曲の外側に居るのではなく、聴いている自分がその楽曲の作り出す世界に入っている感じ。それがグルーブ、たしかに山下達郎のCDを聴いていると演奏している姿や歌っている姿が浮かぶのではなく、その曲の…

ちょっとだけ長めのつぶやき•10ヶ月前

「NP完全」の定義を読んでも分からん

ギズモードの記事で「奇数偶数素数はわかるけど、P≠NP予想がわからない人類は、P≠NP予想やナビエ–ストークス方程式の解がわかるAIに圧倒されるでしょう。」なんていう文言があり、私はP≠NP予想がわからない人間なのでこれが何なのか調べてみました。 www.gizmodo.jp P≠NP予想をネットで調べているとNP完全とNP困難の説明が出てくるわけですが、このNP完全の定義に意味の分からない部分が含まれています。 Wikipediaによれば… (1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題か…