プリクラ問題2

#プリクラ問題 の続き これまでの経緯はこちら http://togetter.com/li/765312 条件は以下の通り。 (1)n人がいる 続きを読む
6
前へ 1 ・・ 12 13
小金井ささら | ユキちゃんかわいい @kgneissr

#プリクラ問題」で検索するとそりゃあプリクラ問題しか出ないけど、「プリクラ問題」で検索するといろんなツイートが引っ掛かって面白い

2015-01-11 01:07:11
すみたつ @Sumitacchan

個人的にはP(n,m)の分布よりもどのような状況のときにP(n,m)を完全に決められるかに興味がある 例えばmが素数冪ならP(m^k,m)=m^(k-1)(m^k-1)/(m-1)だが一般のmではどうか? #プリクラ問題

2015-01-11 01:36:39
すみたつ @Sumitacchan

そういうわけでプリクラ数を計算できる方、P(100,10)とP(121,11)を計算してください #プリクラ問題

2015-01-11 01:38:01
まる @ps_maru

クリーク"辺"被覆問題はクラスNPですが、Wikipedia以外でNP完全なのかどうかが証明されている文献を見つけた方はいますでしょうか…?もしNP完全だとしたら、N=NPでない限り一般解の可能性が絶望的なような…。 #プリクラ問題

2015-01-11 02:17:43
小金井ささら | ユキちゃんかわいい @kgneissr

@ps_maru あ、間違えてました…… [(n-1)/(m-1)]-[n/m]でした……(大違い……) #プリクラ問題

2015-01-11 02:30:16
まる @ps_maru

1月11日14時現在のプリクラ問題のまとめ(1~4ページ/8ページ中) #プリクラ問題 pic.twitter.com/CyfTqTR1cf

2015-01-11 15:08:46
拡大
まる @ps_maru

1月11日14時現在のプリクラ問題のまとめ(5~8ページ/8ページ中) #プリクラ問題 pic.twitter.com/51jopabavC

2015-01-11 15:10:28
拡大
まる @ps_maru

上界P(n,m)≤{1+ln⁡(m(m-1)/2)}n(n-1)/m(m-1)ってどうみてもnCmより雑じゃんと思ってたけど、もしかして完全グラフじゃないグラフにも使えるように設計された上界なんじゃ……? #プリクラ問題

2015-01-11 15:24:57
小金井ささら | ユキちゃんかわいい @kgneissr

「特定のペアだけは絶対に一緒に写らない」としたプリクラ問題 #プリクラ問題

2015-01-11 16:33:03
しぃ @gunshi03

@___3618 結局はこれと顔違うんですけどね? #プリクラ問題

2015-01-11 17:55:26
まる @ps_maru

@ps_maru クリーク辺被覆問題はクラスNPで、(v,k,t)-covering問題は3変数未知ならNP完全であるが、t=2などと固定すると入力がNP完全の問題より少なくなるためNP完全ではないただのクラスNP問題らしいです。一般解の望みは絶たれなかった!? #プリクラ問題

2015-01-11 20:54:18
まる @ps_maru

(7,4,2)は大学入試に出題できる程度のレベルなようだ。 #プリクラ問題

2015-01-11 21:52:19
前へ 1 ・・ 12 13