小金井ささら | ユキちゃんかわいい
@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
まる
@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
まる
@ps_maru
@ps_maru クリーク辺被覆問題はクラスNPで、(v,k,t)-covering問題は3変数未知ならNP完全であるが、t=2などと固定すると入力がNP完全の問題より少なくなるためNP完全ではないただのクラスNP問題らしいです。一般解の望みは絶たれなかった!? #プリクラ問題
2015-01-11 20:54:18