著者

加賀谷 光祐 冨澤 眞樹 遠山 宏明

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J105-D, no.3, pp.144-153, 2022-03-01

---

Lunar Lockoutは解の存在を判定する問題がNP困難であることが知られているスライディングブロックパズルである.また,Generalized Lunar Lockout Variantは動かない駒の使用を認めたLunar Lockoutであり,解の存在を判定する問題はPSPACE完全であることが示されている.本研究では,Generalized Lunar Lockout Variantに対して,各駒の移動回数を高々k回に制限した解が存在するか否かを判定する問題を導入し,k≧ 3のときNP完全であることを証明した.

著者

梅田空大 冨澤眞樹

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告情報システムと社会環境(IS) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.27, pp.69-76, 2006-03-17

被引用文献数

4

---

本稿では,友人の招待で参加するのではなく,ある地域(町内,学区,生活圏)に住んでいるという条件で参加できる地域指向型ソーシャル・ネットワーク・サービス(SNS)を提案する.地域指向型SNSでは,地域に根ざした話題(近所の店,通学路,公共施設など)を単位としたコミュニティを育成し,社会生活に関する問題意識を共有することを目的としている.本稿は,現状のSNSについての仕組みとそれに対する考察,地域指向型SNSの考え方や地域指向型SNSを具体的なモデルを元にした説明,実現に向けての課題などについて述べる.This paper suggest Regional-Oriented Social Network Service (SNS) that have the participation way by not invitation from a friend but condition that SNS user belongs to a particular bit of region as town, school and living sphere. It's an object of Regional-oriented SNS to develop a community based on region-focused topics about local shop, school road and public facility and to share the problem consciousness for social living. This paper describes about that know-how of current SNS and discussion about that, concept and concrete model of Regional-Oriented SNS, and assignment toward the realization of that.