TCP over websocket

仕事の関係でKeycloakとその下回りであるJBoss/WildFlyを調べていて面白い記事を見つけました。

EJB呼び出しなどは以前はRMI/IIOPのようなTCP/IP上のプロトコルを使っていたが、いまはWebSocket上で行っている(TCP over WebSocket)という記事です。これはWildFly8の頃で、現在の12ではまた別のプロトコルに代わっています。

これと並行してKeycloakでWebSocketを保護できるという話を見つけました。

OAuth2のアクセストークンの期限切れをwebsocketに反映させるとかはできないけど、認証だけならアダプタ入れるだけでできるよという話です。
プロトコル的にはまずHTTP 1.1 GETと一緒にUpgrade要求をするので、その間にOAuth2の認可フローを差し込めるというのがプロトコル上の理解です。

上記のような話題からウェブサーバーとしてOpenID connect / OAuth2などと連携するVPN/トンネリング製品ができるなとおもっていたのですが、https://kaazing.com/ というのがまさにそういう製品のようです。

chisel(https://github.com/jpillora/chisel)というgoで作られた、やはり同様のOSSがあったのですが、保護までしてくれないようだったのですが、chiselもApacheのmod_wstunnel / mod_auth_openidcとかと組み合わせればいけそうな気がします。

すこしこのあたりに興味がわいてきました。

俺のFPTの理解

FPTにおいては幅とパラメータが存在する。

たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。
k-クリーク判定では幅hに対しての組み合わせになるので二項定理から {}_{h}\mathrm{C}_{k} = {}_{h}\mathrm{C}_{h-k}なので、 min(k,h-k)を用いて h^{min(k,h-k)}のオーダーで上限を決めることができる。

今回、最大クリーク問題の幅をk-coreとしたが、その幅は彩色数の近似にもできる。
k-coreの順序で貪欲彩色することにより、k-core + 1以下の彩色結果が得られるので、それを幅にしてもよい。
その場合でも上限は幅をもとに計算することができる。

W[1]-completeとはおそらくこの幅hとパラメータkの2変数により f(h,k)p(n)となるものだと考える。幅はアルゴリズム上設定されたもので、kは判定問題に与えられるパラメータ。これが指数関数しかないのか、多項式のものもあるのかはまだわからない。探索木を多項式時間で検索できればよい。結構制限はあるなかでの探索なのでもしかすると多項式時間のアルゴリズムがあるかもしれない。

指数時間アルゴリズム入門だと100万頂点からサイズ30以下の頂点被覆を求めることが可能ってなってたけど、補グラフの最大クリークのサイズをnから引いたものが頂点被覆なわけだから、幅hに対してk,h-kが小さければ、もっと全然できるはず。

Clique problem - Wikipedia 英語のWikiPediaの記事でDegeneracyをつかって最大クリーク問題ができるのが書いてあるな。

指数時間アルゴリズム入門だとkに対してと書いてあるので、2変数はちがうんだろうなとおもう。

なんとなく

最大クリーク問題の f(\Delta_+)p(n)の中身を分解して、\Delta_+多項式になっていることを証明しないとダメな気がしてきた。

わかった。ZPP=EXPTIMEでP≠NPのほうだ

最大クリーク問題つづき

グラフのDegeneracyをkとすると前処理後、おおまか 2^{k}n  で最大クリークが求まるな。

Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフ G(V,E)を順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。

最大出次数を \Delta_+とする。

頂点が順序付けされたので、 vを始点とするクリーク集合というのが扱えるようになった。
頂点 vとその出力辺からなる隣接集合から誘導される部分グラフH_v vを始点とするクリーク集合がすべて含まれる。

このH_vvを除く頂点の組み合わせをすべて試せば、vを含むクリークの最大サイズがわかる。
 \Delta_+は最小化されていて、n頂点すべてについて行うので、大まか 2^{\Delta_+} n でもとまる。

もうすこしアルゴリズムとして分解することにする。

頂点の冪集合P(V)のうち、特にサイズがkのものを P_k(V) \subset P(V)と書く。
fをサイズkの頂点集合がクリークであればkを、そうでなければ-1を返すものとする。これは誘導部分グラフを作成し、頂点数と辺数から決めることができ多項式時間である。
 \displaystyle f: P_k(V) \rightarrow \{k,-1\}

 T_vをある頂点vの出力辺から作成される隣接集合とすると、最大クリークをもとめる \omega(G)は下記のような形になる。

 \displaystyle \omega(G) = \max_{v \in V} \max_{k=0,1,\cdots} \max\{\max \{ f(\{v\} \cup T_v \setminus X),\> f(\{v\} \cup X)\} |  X \in P_{k}(T_v) \}

上記の式は下限、上限から挟み撃ちにしている。

 f(\{v\} \cup T \setminus X) > 0となるときは、明らかに vを始点とする最大クリークであり、次の頂点に移ればよい。最も内側のmax式が-1の時は、下でクリークが見つからないわけなので、そこまでに見つかった最大クリークサイズを返して、やはり次の頂点に移る。*1

判定式のほうはkを求めるクリークサイズとすると d_+(v) - k,kの小さいほうを使用する。これを k'とするとおおまか計算量は {}_{\Delta_+}\mathrm{C}_{k'} nになる。
もちろん k > \Delta_+であれば解はない。

 \displaystyle 
\begin{eqnarray}
\omega(G,k) & = & \max_{v \in V} \max_{X \in P_{k}(T_v)} f(\{v\} \cup X) & \hspace{1cm} & (d_+(v) - t \ge k) \\
                 & = & \max_{v \in V} \max_{X \in P_{k'}(T_v)} f(\{v\} \cup T_v \setminus X) & \hspace{1cm} & (d_+(v) - t \lt k)
\end{eqnarray}

最悪のケースは \frac{\Delta_+}{2} = \omega(G)のときで、例えば K_2が50個あるようなグラフの補グラフだと思う。サイズ50のクリークが2^{50}個あって、98正則グラフなので \Delta_+ = 98。正確に半分ではないけどイメージは伝わると思う。これは補グラフが連結ではないことが頂点数、辺数からわかるので状況に合わせて必要な処理を組み込むことで平均的な時間はもっと高速化できる。
おそらくこのアルゴリズムはZPPである。
まとめ

自分の理解ではおそらくNP困難問題である最大クリーク問題がPであり、NP完全問題であるk-クリーク問題がFPTになった。
もし違う観点があるとすれば、最大クリーク問題が f(\Delta_+)p(n)のFPTで、k-クリーク問題が f(\Delta_+,k)p(n)のFPTという感じ。

最大次数やk-core数なんてデータの入力長に依存しないのでPだと思っている。が、アルゴリズムで設定された幅とみれば、それは指数時間なのかもしれない。

その他
従来のFTPの議論では最大クリークや最大独立集合にFPTがないといわれていたが、次数から引くというとのが盲点だったのかなと思った。
ただ無向グラフでvを含むクリークの最大を全部数えるでも、おそらくここに行きつくので最大次数は最小化できないという意味で有向グラフに変換するというが転換だったなのかなと思う。

(以下、全部 たぶん)

P≠NP予想は否定したとおもう。
#PもPである。P=NPであったので多項式階層はすべて潰れた

そしてP=ZPPである。P=ZPPからZPP≠EXPTIMEになる。
P=NPなのでETH, SETHも否定した。


参考 : NP困難 - Wikipedia
参考: #P - Wikipedia
参考: P≠NP予想 - Wikipedia
参考: 多項式階層 - Wikipedia
参考 : Fixed Parameter Algorithms Open lectures for PhD students in computer science
参考: ZPP - Wikipedia

*1:ただ、なんとなく中央まで行くのではなくて、3分の1進めたところで下限のほうのクリークの集合から2つ選んで最大クリークを探すほうが良い気がする。

K4の対辺をつなぐ話(2)

前、こういうのを考えて、最大クリーク数もなんとなく半分になりそうって書いたんだけど、
kousuke.hatenablog.com

それって式にするとこういうことになるのかな?
 \chi(f(K_n)) = \lfloor \frac{\chi(K_n) }{2} \rfloor

fは G(V,E)の辺を頂点にして、 e_i \cup e_j K_4の時に辺とするような変換。
完全グラフについては証明できそうだけどな。


一般のグラフでも下記の形で成り立つとすれば
 \chi(f(G)) = \lfloor \frac{\chi(G) }{2} \rfloor

これを繰り返して、最大クリーク数が 2^n \le \chi(G) \lt 2^{n+1}の範囲で求められそうとおもったよ。

保育士は「誰でもできる仕事」か?について

news.yahoo.co.jp

でこの記事に対して、下記のようなブクマコメントをしたのだけれど、1つではあるけれど、スターがついてしまったのでメモ代わりに書いておこうとおもう。

保育士は「誰でもできる仕事」か(駒崎弘樹) - 個人 - Yahoo!ニュース

ホリエモンは保育士が特に資格が必要な職業とは思えないからって発言だろうなと思う。準保育士とかつくって、要件緩和、違いを明確化すればよい案件かもしれない

2017/10/17 14:12

そもそも保育士が難しいというのは下記のエントリが分かりやすく、保育士試験の合格率は2割程度となっている。
www.lifeworkshare.com

で駒崎さんのブログ中にある。
法的に最低人員配置基準を決められている & 物理的に無理と書いてある部分を満たそうとすると無理という話なんだけど、
これ0歳児3人に1人つけなきゃいけない法的基準を、0歳児20人に保育士2人+バイト6人くらいにできないの?というのは自分としても思う。

さすがにまったくの未経験者は厳しいと思うので、先の保育士試験で筆記の科目合格の人たちを準保育士としてはどうかみたいなヨタ話として書いた。

もともとの本題のなぜ給与が上がらないかについては、駒崎さんの書いている通り、構造上の問題だとおもう。

ただ、ホリエモンの答えにキチンと反論するなら、保育士に必要な知識がたくさんあることは書かないといけないし、実際の業務すべてにその知識が必要なこと(すべて保育士がやらないといけないこと)を示さないといけない。

で、個人的にはそうだとはおもわない。法律上そうなっているのはわかるが、すべて保育士がやらないといけないということはさすがに示せないとおもう。実際には保育士未満の人で肩代わりできる仕事は結構あるだろう(という思い込みかもしれないけど)、もしそうなら法律かえればいいんじゃね。とおもう。

駒崎さんの最後の給与を上げる方法についていえば、「補助金を増やせば保育士給与は上がる」は正しいだろうけど、それは経済活動上望ましくはないなとおもう。
また足りていないのは首都圏のみという話もあるので、であればまさに特区で規制緩和でいいんじゃないだろうか?

選挙とか

興味はもつのだけれども、投票したい政党とかがないなぁ。

  • 二大政党制とか目指すのやめたほうがいいんじゃないの?とおもってきた。

STOP安倍政権のスローガンとかみていると、そもそも単独政党による過半数とかできるルールが悪いんじゃないかとおもってきた。いっそのこと、政党助成金の上限を決めたり、政党の議員上限数を決めたりで自民党なら派閥単位で分党とか、単独与党は存在しないようにしたほうがいいんじゃないだろうか?

  • 解散権はあっていいとおもうけど、政局によって総選挙のための費用を負担させられるのは微妙

そもそも任期を務め上げるというのは前提にないといけないと思う。なので時限立法について選挙後、新首相による廃案可能権を付与するとか、そういうハザードを課してはどうかとおもう。

憲法改正はあってもよいとおもうのだけど、それが議席数による数の暴力と称されるようなプロセスであれば、不満はあるし、でも必要であれば迅速には対応してほしいとはおもう。結局3分の2の賛成多数で成立のような常に1/2の選択を選挙にかこつけて押し付けられているのがむしろ暴力的と感じている気がする。
なので、憲法改正は時限立法としてまずは試してみて、一定期間後に憲法に反映されるというようなプロセスはあっていいとおもう。

で、個人的にはこういうアーキテクチャとかルールが一番興味があって、政治をリファクタリングするというような政党がほしいのだとおもった。
それは希望の党がいうような「リセットする」とか、しがらみを否定するものではなくて、不満(おそらく課題ではなく)は何で、それはこういうルールにすればうまくいくんじゃないだろうか?というのをコード化(法制化)することで妥当なプロセスに落ち着くように、アーキテクチャを作ってくれる人達、そういうことを考えてくれる政党がほしいなとおもう。

それは見る感じ、すこし立憲民主党ではなさそうでだから投票したい政党がないという風になるのだと思う。