クラスMAX SNPのソースを表示
←
クラスMAX SNP
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、以下のグループに属する利用者のみが実行できます:
登録利用者
。
このページは編集や他の操作ができないように保護されています。
このページのソースの閲覧やコピーができます。
'''【くらすまっくすえすえぬぴー (class MAX SNP)】''' 厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数<math>\epsilon\,</math>を与えれば, <math>(1/\epsilon)\,</math>と入力の大きさの多項式時間で, 近似率<math>\epsilon\,</math>の解を求められる場合がある. しかしMAXSNP困難な問題は, <math>\mbox{P}\neq \mbox{NP}\,</math>という仮定の下では, 多項式時間で近似率<math>\epsilon\,</math>の近似解を求められるような<math>\epsilon\,</math>に限界がある. [[Category:組合せ最適化|くらすまっくすえすえぬぴー]]
クラスMAX SNP
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
最近の更新
おまかせ表示
ヘルプ
ORWikiへのお問い合わせ
OR学会HP
OR学会アーカイブ集
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報