fromageの日記 | スラド

fromageの日記：ハッシュ関数の証明と wikipedia の説明の食い違い 1

日記 by fromage 2017年08月30日 0時03分

メルカリの技術ブログに、Knuth multiplicative hash が最小完全ハッシュ関数であることの証明が掲載されています。一方、Wikipedia 英語版の完全ハッシュ関数の項目には、

In computer science, a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions.

とあり、（最小でなくても）完全ハッシュ関数であれば、要素の写像先で衝突がない、とされています。そして、Wikipedia 英語版のmultiplicative hashingの項目を見ると、

Multiplicative hashing is a simple type of hash function often used by teachers introducing students to hash tables.[11] Multiplicative hash functions are simple and fast, but have higher collision rates in hash tables than more sophisticated hash functions.[12]
（略）
[11] Knuth. "The Art of Computer Programming". Volume 3: "Sorting and Searching". Section "6.4. Hashing".

とあり、ハッシュテーブルを紹介するのに使われ、簡潔で高速だが、より洗練されたハッシュ関数より高い衝突率を持つ、と説明されています。

Multiplicative Hashing を直接説明しているのではないのですが、ニューヨーク市立大学の Weiss 教授による講義資料 (PDF) では、5.3 Collision の中で、

Since almost all practical hash functions are not perfect, they will map one or more keys to the same indices...

ほとんどの実用的なハッシュ関数は完全ではなく、異なるキーを同じインデックスに写像することがある、と書いてあるので、この証明が正しければ非常に重要な結果だと思います。

メルカリの技術ブログには multiplicative hash の手順が示されている一方、Wikipedia には文章での説明だけなので、名前が似ているが違う手順を指している可能性があります。また、何らかの条件下で成り立つのかもしれません。証明を読んだらわかるかな。

fromageの日記： P vs. NP 論文の間違いの具体的な指摘

日記 by fromage 2017年08月19日 16時34分

ストーリーにもコメントしましたが、日記にも書いておきます。

P vs. NP の論文が検証されている中で、間違いの具体的な指摘が2つ出てきました。

(1) 検証されている論文の中で基盤となっている先行研究を行った研究者である Alexander Razborov 教授が、論文中の矛盾を指摘しました（Razborov 教授の知人による投稿, それを紹介している山形頼之氏のツイート）。

今回の論文が参考にしている先行研究である Berg and Ulfberg による議論（単調回路に対する下界を示すのに CNF, DNF の両方を使う方法）は Tardos の関数についても成り立つが、それは今回の論文の定理 6 と矛盾するので、この論文は必然的に間違いになる、と説明されています。

(2) 今回の論文の定理 6 の証明における帰納法に誤りがある（詳細、山形頼之氏のもう1つのツイート）とのことです。

コメントはストーリーの方にお願いします。

fromageの日記： arxiv に P vs. NP 問題を解決した論文が投稿される 52

日記 by fromage 2017年08月15日 22時46分

計算機科学の未解決問題である P vs. NP 予想を解決したとする論文が、論文投稿サイトである arxiv に投稿された（結城浩氏のツイート、論文のページ）。

NP 完全問題は、例えば、巡回セールスマン問題のような、入力（重み付きグラフと閾値）に対する証拠（巡回経路）があれば、入力を多項式時間で判定できる問題の中で、最も難しいものである。NP 完全問題を多項式時間で解くアルゴリズムはまだ見つかっていない。そのようなアルゴリズムが存在すれば、P = NP であり、存在しないならば、P != NP であるが、現在までどちらなのか分かっていない。

今回投稿された論文では、P != NP （つまり、NP 完全問題は多項式時間で解けない）と結論付けている。著者が計算機科学の専門家（大学の情報科学科の教授）である点から、この論文に期待する意見もある。しかし、arxiv には査読の仕組みがないため、この証明が正しいかどうかは、現段階では不明である。

ところで、P vs. NP 問題を解決したと主張する論文のリストを示しているページによると、（査読を通ったものを含めて）116本の論文がこれまで発表されている。

fromageの日記：ルービックキューブはNP完全問題 0

日記 by fromage 2017年07月20日 23時13分

Gizmodo から。

色のついていない部分がある n x n x n の一般化ルービックキューブ RCm に対して、k 回以内の回転で、6面とも色を揃えられるかどうかを判定する問題が NP 完全であることは知られていた。今回は、全部に色がついている n x n x n の一般化ルービックキューブ RC に対して、k回以内の回転で 6面とも色を揃えられるかどうかを判定する問題が NP 完全であることが示された。

ハミルトンパス問題の変形（この NP 完全性も示されている）から、このルービックキューブ問題への多項式時間還元を示すことで証明されている。

でも記事内にあるように、NP 完全問題であっても、ルービックキューブは n = 3 で固定されているので、実際に解くことができる。

fromageの日記：クイズの難しいほうの答えを見つける簡単な方法 6

日記 by fromage 2017年07月19日 23時58分

知能検査と称した計算問題の2つ目（難しいほう）の解答を見つける方法が難しく説明されていたので、簡単な方法をメモ。

問題は次の通り。

1+4 = 5
2+5 = 12
3+6 = 21
8+11 = ?

以下は、ネタバレになります。

左辺を見ると足す数が 1, 2, 3, 足される数が 4, 5, 6 と1つずつ増えています。右辺はそれぞれ 7, 9 と増えています。
これらは、左辺の足す数、足される数が１ずつ増えるとき、右辺の値の増加量が線形に増えていくと見なすことができます。
ここから、
4+7 の右辺は 21 + 11 = 32,
5+8 の右辺は 32 + 13 = 45,
6+9 の右辺は 45 + 15 = 60,
7+10 の右辺は 60 + 17 = 77,
8+11 の右辺は 77 + 19 = 96
となり, 答えは 96 になります。