パスワードを忘れた? アカウント作成
2014年9月 記事 / 日記 / コメント / タレコミ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2014年9月9日のタレコミ一覧(全14件)
11550019 submission
数学

/.Jに聞け:【助けて】 P≠NPの証明、これで合ってる?(第二回)

タレコミ by fiercewinds
fiercewinds 曰く、
先日はコメントありがとうございました。

頂いた指摘事項を元に、P≠NPの証明をアップデートしました。
また、反論とその回答も追加しています。

引き続きコメントいただければと思います。

_____________________________________________________________
○条件(使用する公理)
  • ZFC
  • 計算モデルはチューリングマシン(TM)とする。
    証明の簡単化のため等価な回路族も使用する。
  • 複雑性クラスは集合とする。
  • 漸近的解析は複雑性クラスの分離のみ成立する。
    つまり、時間・空間階層定理は成立するが、
    ∀x,y∈P(x∨y∈P)|P:複雑性クラス
    が成り立つとは限らない。

_____________________________________________________________
○証明

・定理1
(∀p,q∈P(p∨q∈NP))∧(∃x,y∈P(x∨y∉P))
→(P≠NP)

証明
関数の出力の一意性より明らかなため省略する。


・定理2
∀p,q∈P(p∨q∈NP)

証明
TMの構成より、P問題を計算する決定性TMを複数まとめたものはP問題と同じ計算資源を使う非決定的TMになる。よってNP問題となる。


・定理3
(∀r∈P(¬r∈P))→(∃x,y∈P(x∨y∉P))

証明
背理法を用いて証明する。
¬(∀r∈P(¬r∈P))→(∃x,y∈P(x∨y∉P))
= (∀r∈P(¬r∈P))∧(∀x,y∈P(x∨y∈P))
と仮定する。

簡単のためTMと等価な回路族を使用する。

Pは、回路族の各回路の射影関数
Pp(n,k)(w)=
{入力長がnの場合、k文字目の値を出力する
{入力長がn以外の場合、偽の値を出力する
Pn(n,k)(w)=
{入力長がnの場合、k文字目の値の否定を出力する
{入力長がn以外の場合、偽の値を出力する
を含む。

よって、
Pp(n,k)(w)∈P
Pn(n,k)(w)∈P
(∀r∈P(¬r∈P))∧(∀x,y∈P(x∨y∈P))
であり、これは回路族の再帰的定義と一致する。

よってPは回路族全体と等しく、P=Rが成立する。
しかし、時間階層定理よりP≠Rであり、P=Rと矛盾する。

したがって、背理法より
(∀r∈P(¬r∈P))→(∃x,y∈P(x∨y∉P))
が成立する。


・定理4
∀r∈P(¬r∈P)

証明
決定性TMの構成より、P問題の真偽が逆のTMはP問題と同じ計算資源を使う決定性TMになる。よってP問題となる。


・定理5
(∃x,y∈P(x∨y∉P))

証明
定理3、4より明らかである。


・定理6
P≠NP

証明
定理1、2、5より明らかである。

以上で証明は完了しました。

_____________________________________________________________
○反論とその回答

反論1
複雑性クラスでは定数倍の計算資源増加は無視するから、∀x,y∈P(x∨y∈P)とならないのはおかしい。

回答
本証明では、通常の計算複雑性理論から「漸近的解析で同じ複雑性となる複雑性クラスは同じクラスになる」という公理を外しているため、定数倍の計算資源増加を無視できるかどうかは定まっていない。
上記の通り、この公理無しで∃x,y∈P(x∨y∉P)が証明出来ているため、漸近的解析を根拠に∀x,y∈P(x∨y∈P)とすると計算モデルと矛盾する。


反論2
この証明の系としてPSPACE≠NPSPACEとなるが、これはSAVITCHの定理と矛盾している。

回答
SAVITCHの定理は、漸近的解析を用いて定数倍の計算資源増加を無視しているため、PSPACE≠NPSPACEとなる。
SAVITCHの定理も、正確には
 NSPACE(f(n)) ⊂ SPACE(f^2(n))
のため、定数倍の計算資源増加を無視しなければPSPACE≠NPSPACEとならないかもしれない。


反論3
定理3において背理法の仮定からP=Rを導いているが、問題の無限個の論理和を用意しない限りこのような結論にならないはずだ。

回答
背理法にて∀x,y∈P(x∨y∈P)と仮定することにより、(本来ならばありえない)問題の無限個の論理和を仮定の中で実現している。


反論4
定理3において、証明にありえない条件(問題の無限個の論理和を含む問題)を使用しているから、証明になっていない。

回答
問題の無限個の論理和はあくまで背理法の仮定の中で発生する。背理法によりこの仮定は否定されるため、Pの中には問題の無限個の論理和を含む問題は存在しない


反論5
有理数と無理数の関係(有理数の有限和は有理数のまま)を考えると、問題の無限個の論理和を含む問題を実際に構成しない限りはこの証明は成り立たないはずだ。

回答
有理数と無理数は濃度が異なるが、PとNPは同じ濃度のため、その論法は成り立たない。

11551036 submission

NTTドコモから顧客の管理情報が流出、社員個人宅住所も含む

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
NTTドコモから、その顧客の管理情報が流出した可能性があることが発表された(報道発表)。

これによると、流出したのは保守運用サービス「法人モバイル管理サービス」を提供するために顧客から預かっていた情報で、1社1,053名分の社員の個人宅住所を含む管理情報(法人名、業務用携帯電話番号、業務用携帯電話の利用者名、住所等)だという。

流出経路は明らかになっていないが、「外部からの不正アクセスによる管理情報の流出はない」という。また、捜査機関へも相談させていただいており、被害届提出の準備も行っているとのことだ。
11551058 submission

スクエニがゲームストリーミングサービスを発表、FF7などを配信へ

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
スクウェア・エニックスがクラウドゲーミング技術を使ったゲーム配信サービス「DIVE IN」を10月9日より開始する。専用アプリを使い、スマートフォンやタブレットからゲームをプレイできる。サービス開始時には「FINAL FANTASY VII International」や「FINAL FANTASY XIII」、「Season OF Mystery:The Cherry Blossom Murders」の3タイトルがプレイできる。価格はそれぞれ200円/3日、250円/3日、150円/月(すべて税別)。

なお、FF7や8はPC版もリリースされており、Season OF Mystery:The Cherry Blossom MurdersについてはもともとPCゲームだったが、FF13についてはPC版は発売されていない。まさかクラウドゲームのバックエンドにPS3やXbox 360を使うとは思えないのだが、公開されていないPC移植版が存在していたりするのだろうか。
11551123 submission
マイクロソフト

PCにバンドルされるOfficeのライセンス形態が変わる?

タレコミ by hylom
hylom 曰く、
国内ではMS OfficeがバンドルされているPCが少なくないが、このバンドル版Officeのライセンス形態が今後変わるという。現在はそのPCでのみ、そのバンドルされているバージョンのOfficeが利用できるという制限があったが、今後はそのPCを使っている限り無償でバージョンアップも可能で、さらにOffice 365のサブスクリプションライセンス1年分も付属する、という形になるという(PC Watch)。

具体的には、今後バンドルされるOfficeは「そのPCから利用する限りは永続的に利用できるOffice 365」になるとのことで、単体で販売されているOffice 365と同様に無償でのアップデートが可能になる。さらにタブレットなどそのPC以外でも利用できるOffice 3365の1年分のサブスクリプションも付属する。さらに、いままでプリインストール版のOfficeを使っているユーザーについても、新しいバージョンへのアップデートが無料で可能になるという。

これらは「関係者からの情報」とのことで正式に発表されたものではない。そのため、正式にどうなるかは分からないが、少なくとも制限が現在よりもきつくなる方向には向かわないようだ。
11551236 submission

IPAのセキュリティ対策キャンペーンテーマから「ID・パスワードは定期的に変更する」が消える

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
IPA(情報処理推進機構)が、て「ID・パスワードのセキュリティ対策」をテーマとした広告企画コンペを行うようなのだが、「ID・パスワードのセキュリティ対策」の内容が話題になっている(公募要領PDF)。公募の内容は以下の様なもので、セキュリティを啓蒙する広告自体に異論は無いのだが、突っ込まれているのは「ID・パスワードは定期的に変更する」というところだ。

以下の対策事例いずれかを用いて「ID・パスワードのセキュリティ対策」をテーマにした広告展開を企画・実施し、対策実施への行動喚起を促す。(使用する対策事例は複数も可)
・「ID・パスワードは定期的に変更する」
・「サービスごとに異なるパスワードを設定する」
・「パスワードはわかりにくい文字列(8 文字以上、記号を含む)を設定する」

Twitter上ではこの「パスワードの定期的な変更」について議論になっていたが(twitterセキュリティネタまとめ)、ツッコミを受けてか9日には公募要領の内容が修正され、テーマから「ID・パスワードは定期的に変更する」 という個所は削除されている。

11551351 submission

Amazon、同社のスマートフォン「FirePhone」を99セントに

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
Amazonが新型iPhoneへ対抗してか、同社のスマートフォン「FirePhone」を99セントで販売するとのこと。これはAT&Tとの2年契約時の価格で、契約無しの場合は449ドル(日経新聞)。

なお、当然ながら99セントでの日本からの購入は不可。

情報元へのリンク
11551361 submission

コンビニ店員を土下座させて商品を脅し取る様子を撮影しネットに公開した男、逮捕される

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
大阪府のコンビニで、店の経営者に対し土下座を強要し、さらに商品を脅し取った男性が逮捕された。この男性はその様子を動画投稿サイトに投稿していたという(NHKニュース)。ITmediaによると、この動画に対しネットで批判が相次ぎ「炎上」。投稿者や関係者の個人情報がさらされる事態になっているという。
11551435 submission
宇宙

小惑星2014 RC、破片が地球に落下していた?

タレコミ by KAMUI
KAMUI 曰く、
日本時間の8日3時すぎに地球から4万キロを通過した小惑星「2014 RC」だが、BBCの記事などに依ると中央アメリカのニカラグアに一部が落下していた模様。

落下地点はニカラグアの首都・マナグアにあるアウグスト・セサル・サンディーノ国際空港近傍の雑木林で、直径12メートル・深さ5メートルのクレーターが出来たそうだ。人的被害が出なかったのは僥倖としか言えませんな・・・
11551437 submission

AT&T曰くブロードバンドは4Mbpsで十分、10Mbpsじゃ速すぎ…?

タレコミ by taraiok
taraiok 曰く、
AT&TとVerizonは、連邦通信委員会(FCC)に対し、ブロードバンドの定義を最大4Mbpsから10Mbpsへは変更しないよう要望した。AT&Tによれば、10Mbpsのサービスは大多数のアメリカ人が求める速度を超えているのだという。VerizonもこうしたAT&Tの意見に同調している(arstechnicaslashdot)。

そのほかのケーブルネットワーク企業はコメントを出さなかった。しかし、全国ケーブル通信協会(NCTA)は、1~4Mbpsの通信速度は、通信関連法に定められた「高品質な音声、ビデオおよびデータの利用」といった用途には十分であるとして、ブロードバンドの速度に関する定義を変えないよう要望したとしている。
11551537 submission

コーヒーの原料となるコーヒーノキのゲノム解読に成功

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
11か国の研究者らが参加した国際研究プロジェクトにより、コーヒーの原料となるコーヒーノキのゲノムの解読に成功したそうだ。この解読結果を活用すれば、味を向上させるだけでなく、干ばつや病気に対する耐性を高めたコーヒーノキのより頑強な品種を開発できるかもしれない。コーヒー輸出国の上位には、多くの中米諸国が名を連ねているが、現在、1976年以降で最悪規模の赤さび病流行が発生しており、コーヒーノキの約半数が被害を受けている。

情報元へのリンク
11551565 submission

Blockchainに永遠に言葉を残そう

タレコミ by Anonymous Coward
あるAnonymous Coward 曰く、
いささか旧聞に属するが、過日ProofOfMeなるサービスが立ち上がった。

仮想通貨では全ての取引記録がBlockchainとして保存される。このBlockchainはどこか特定のサーバに依存して保管されているのではなく、P2Pネットワークの全参加者によって保持されており、事実上改竄不可能なデータベースといえる。

ProofofMeはこのBlockchainにメッセージを残すというシンプルなサービスで、Blockchainの革命性を示したいという思いで開発したとのことだ(http://nomad-ken.com/3385)。

こうした、管理主体が存在せず改竄不可能なデータベースの応用例として、ほかにDNSに応用したNamecoinや暗号化メッセージを送るBitmessageなどが開発されている。

/.Jの諸氏なら、どんなサービスを思いつくだろうか。またどんな情報をBlockchainに残してみたいだろうか。

情報元へのリンク
11551665 submission
日記

続・金髪たれちち巨乳めがね ~台湾からの刺客篇~

タレコミ by route127
route127 曰く、

クラウディア窓辺28歳(再来月で29)に強力なライバルが出現したらしい
なんでも藍澤光がSilverlightからAzureにコンバートされたとのこと。
しかもそれを9月9日、大陸の老人節に合わせて発表するという、まさに「オバハンにはご退場願おう」と言わんばかりの行いである。
小娘と思って油断していたら足元をすくわれるぞたれちち!
Azureクイーンの座を巡る戦いの火蓋は今まさに切って落とされた!!

typodupeerror

吾輩はリファレンスである。名前はまだ無い -- perlの中の人

読み込み中...