stanford-oval/wikipedia huggingface dataset:
重久剛一
出演 > テレビドラマ > 日本テレビ

「十手無用 九丁堀事件帖」第13話（1975年12月28日）
「桃太郎侍」
第19話「中仙道・鬼狩り道中」（1977年2月13日） - 源六
第38話「甘い言葉に罠がある」（1977年6月26日） - 銀蔵
第54話「闇をさく妖剣」（1977年10月16日） - 久造
第72話「絵筆に賭けた命」（1978年2月26日） - 仙八
第85話「女金貸し鬼より怖い」（1978年5月28日） - 丑松
第96話「父娘を結ぶ赤い布」（1978年8月13日）
第126話「看板娘を狙う鬼」（1979年3月18日） - 政吉
第145話「鯛より旨い鰯の人情」（1979年7月29日） - 阿部家御膳番
第164話「お袋さんと呼ばれたい」（1979年12月9日） - 佐五蔵
第187話「旅は道連れ世は無情」（1980年5月18日） - 丑
第201話「当るも八卦当らぬも八卦」（1980年8月24日）
第215話「生みの親より育ての親か」（1980年11月30日）
第224話「邪剣に勝った瓦版」（1981年2月8日） - 彦松
第241話「赤い首輪をつけた猫」（1981年6月7日） - 庄吉
「松平右近事件帳」第2話（1982年4月4日） - 悟作
火曜サスペンス劇場
「影なき殺意」（1982年6月22日）
「原子炉の蟹」（1987年11月17日）
「京都・女性記者シリーズ」第3作（1990年3月20日）
「弁護士・朝日岳之助」第2作（1990年5月29日）
「眠れぬ夜のために」（1991年10月29日）
「警視庁鑑識班」
第1作「ネジと花粉とライターの石 殺人現場の微細な遺留物が真犯人を追いつめる」（1996年5月14日）
第2作「指紋、鏡の破片、血染めの貝殻 ― 殺人現場の遺留物が語る真犯人の心のひだ」（1996年12月3日）
木曜ゴールデンドラマ → ドラマシティ'92
「私が殺した女」（1982年8月19日） - 刑事
「目撃者ご一報下さい」（1983年7月21日）
「悪霊の午後」（1992年5月14日）
長七郎江戸日記シリーズ
「長七郎江戸日記 第1シリーズ」
第8話「風流五三の桐変化」（1983年12月6日） - 店者
第45話「瓦版始末記」（1985年1月8日） - 七兵衛
第60話「大江戸女番長始末記」（1985年5月7日） - 六助
第79話「心はひとつ義兄弟」（1985年12月10日） - 佐吉
第92話「望郷子守唄」（1986年3月18日） - 島造
「長七郎江戸日記 第2シリーズ」第30話（1988年11月8日） - 伝八
「長七郎江戸日記 第3シリーズ」第28話（1991年6月11日） - 佐渡吉
「ハロー!グッバイ」第12話（1989年7月21日）'
八百八町夢日記シリーズ
「八百八町夢日記 第1シリーズ」
第14話「ねの字小僧参上」（1990年1月30日） - 唐獅子の甚兵衛
第18話「最後の涙」（1990年2月27日） - むささびの茂助
「八百八町夢日記 第2シリーズ」
スペシャル1「みちのく忠臣蔵」（1991年10月8日） - ならず者
スペシャル2「国盗り夢物語」（1992年3月24日） - 葛丸
「刑事貴族2」第9話「スイートメモリー」（1991年6月14日） - 事務長
「半七捕物帳」第2話（1992年10月20日） - 六造
「闇を斬る!大江戸犯科帳」第7話（1993年4月20日） - 弥助
出演 > テレビドラマ > TBS

「風」第4話（1967年10月25日）
「海の次郎丸」第22話（1968年8月2日）
大岡越前シリーズ
「大岡越前 第2部」第9話（1971年7月12日） - 仙吉
「大岡越前 第3部」第21話（1972年11月6日） - 留吉
「大岡越前 第6部」第2話（1982年3月15日） - 番人
「大岡越前 第7部」第21話（1983年9月12日） - 銭屋の番頭
「大岡越前 第8部」第20話（1984年12月3日） - そばや
「大岡越前 第9部」第15話（1986年2月3日） - 熊三
「大岡越前 第10部」第17話（1988年6月20日） - 久兵衛
必殺シリーズ
「必殺仕掛人」第21話（1973年1月20日） - 岡っ引き文造
「必殺仕置人」
第14話「賭けた命のかわら版」（1973年7月21日） - 卯平
第22話「楽あれば苦あり親はなし」（1973年9月15日） - 平吉
「助け人走る」
第1話「女郎大脱走」（1973年10月20日） - 常吉
第7話「営業大妨害」（1973年12月1日）
影同心シリーズ
「影同心」第1話（1975年4月5日） - 八百梅の主人
「影同心II」第17話（1976年2月7日）
江戸を斬るシリーズ
「江戸を斬るII」第26話（1976年5月3日） - 瓦版屋
「江戸を斬るIII」第2話（1977年1月24日） - 中間
「江戸を斬るVII」
第6話「桃の節句の鬼退治」（1987年3月2日）
第12話「裏切り盗っ人仁義」（1987年4月13日） - 連蔵
水戸黄門シリーズ
第7部
第1話「水戸から消えた黄門さま」（1976年5月24日） - 百姓
第9話「群狼の罠」（1976年7月19日） - 北海屋の手下
第10話「吼えろ!! 北海の火縄銃」（1976年7月26日） - 北海屋の手下
第19話「最上紅花恋の唄」（1976年9月27日） - 新田屋の番頭
第8部
第10話「命賭ける時」（1977年9月19日） - 中間
第14話「飛龍の火祭り」（1977年10月17日） - 猟師
第12部
第4話「兄と呼ばれた格之進」（1981年9月21日） - 大島屋番頭
第20話「悲願叶えた糸車」（1982年1月11日） - 利助
第13部
第11話「悪を縛った伊賀の組紐」（1982年12月27日） - 善作
第16話「死を賭けた裏切り」（1983年1月31日）
第14部 第4話「わがまま姑の嫁いびり -白石-」（1983年11月21日） - 徳三
第15部 第23話「鬼庄屋にされた黄門様 -篠山-」（1985年7月1日） - 百姓
第16部
第26話「おてんば姫君七変化」（1986年10月20日） - 宿の主人
第28話「娘を救った偽黄門」（1986年11月3日） - 三十
最終話「旅遥か 恋の船唄」（1987年1月19日） - 鹿島屋番頭
第17部
第6話「悲願仇討ち傘女房」（1987年10月5日） - 熊五郎の子分
第14話「馬が蹴散らす悪企み」（1987年11月30日） - 熊
第18部 第28話「印籠盗んだ女掏摸 -清水-」（1989年3月27日）
第20部 第43話（1991年9月2日） - 勘助
第21部 第30話（1992年10月26日） - 仙造
第22部 第6話（1993年6月21日） - 団七
第23部 第8話（1994年9月19日） - 虎松
第24部 第6話（1995年10月23日） - 金八
第26部 第25話（1998年8月10日） - 蔦屋鬼政
第27部 第12話（1999年6月7日） - 三崎屋儀兵衛
「翔んでる!平賀源内」第10話（1989年7月10日）
月曜ドラマスペシャル
「拝啓オグリキャップ様」（1991年9月30日）
「美人秘書の秘密」第2作（1993年6月21日） - 藤岡
「君は今どこに」（1994年9月5日）
「サラリーマン金太郎 第3期」第1話 - 第4話（2002年1月6日 - 1月27日） - 柏木
出演 > テレビドラマ > フジテレビ

「銭形平次」
第23話「闇夜の目」（1966年10月5日） - 三吉
第358話「唄が殺しを呼んでいた」（1973年3月14日）
第409話「江戸と田舎の若旦那」（1974年3月6日） - 伊太八
第420話「浪花男の江戸の夢」（1974年5月22日） - 伊太五郎
第438話「大江戸二十四時」（1974年9月25日） - 銀次
第468話「打首待った!」（1975年4月30日） - 丑松
第474話「おみくじは凶と出た」（1975年6月11日） - 丈吉
第501話「卍 蜘蛛」（1975年12月17日） - 伊太八
第507話「消えた証文」（1976年2月4日） - 留造
第521話「平次一番勝負」（1976年5月12日） - 梅吉
第530話「風前の灯」（1976年7月14日） - 仙蔵
第545話「屋形船の殺人」（1976年10月27日） - 亀造
第556話「居酒屋」（1977年1月22日） - 寅松
第564話「狙われた獄門首」（1977年3月9日） - 島造
第581話「吉凶うらおもて」（1977年7月13日） - 亀蔵
第601話「父と娘」（1977年12月14日） - 仙吉
第621話「しのぶ河岸」（1978年5月3日） - 喜助
第663話「誰がための十手」（1979年3月14日） - 喜助
第700話「みなし児の詩」（1979年） - 和泉屋の番頭
第703話「想い出の紙風船」（1980年1月23日） - 藤吉
第713話「大江戸大地震」（1980年） - 与平
第759話「浮世がからんだ一番富」（1981年3月18日） - 倉松
第818話「五年目の恩讐」（1982年） - 銀次
第850話「死者は夜歩く」（1983年） - 久七
第868話「七つの顔の平次」（1983年10月26日）
「新 三匹の侍」第9話（1970年8月31日）
「木枯し紋次郎 第2部」
第14話「明鴉に死地を射た」（1973年2月17日）
第16話「和田峠に地獄火を見た」（1973年3月3日） - 芳三
最終話「上州新田郡三日月村」（1973年3月31日）
「ぶらり信兵衛 道場破り」第30話（1974年5月2日）
「座頭市物語」第5話（1974年10月31日）
「痛快!河内山宗俊」
第7話「御祝儀放免」（1975年11月17日）
第10話「鬼より怖い奴がいた」（1975年12月8日）
第21話「妻恋い、母恋い風ひとつ」（1976年2月23日）
「夫婦旅日記 さらば浪人」
第1話「雨あがる」（1976年4月5日）
第5話「母の峠路」（1976年5月3日）
第13話「暮れ六ツの鐘が鳴る」（1976年6月28日）
「お耳役秘帳」第13話（1976年6月29日）
「新・座頭市」シリーズ
「新・座頭市 第2シリーズ」第4話（1978年1月30日）
「新・座頭市 第3シリーズ」第16話（1979年8月20日） - 番頭
「江戸の波濤」（1979年12月12日）
「江戸の用心棒」
第1話「三人の命知らず」（1981年4月2日）
第18話「浮気の現場」（1981年7月30日）
時代劇スペシャル
「刺客街道」（1982年5月28日）
「薩摩飛脚」（1982年6月11日）
「御金蔵破り」第3作（1983年1月14日）
「旗本退屈男」（1983年2月25日）
「剣客商売」第2作（1983年3月4日）
「乾いて候」第1作（1983年6月17日）
「怪猫有馬御殿」（1983年8月12日）
「隠密くずれ」第4作（1983年8月26日）
「樅ノ木は残った」（1983年12月1日）
「影の軍団IV」第8話（1985年5月21日）
「泳げ! 第5コース」（1986年4月11日 - 10月31日）
「散歩する霊柩車」（1990年7月30日 - 8月3日）
男と女のミステリー「冬の花 悠子」（1990年8月24日） - 源吉
出演 > テレビドラマ > テレビ東京

「絵島生島」最終話（1971年12月25日）
「紫頭巾 紫頭巾事件帖」
第2話「御用船炎上」（1972年4月13日）
第17話「岡っ引き殺人事件」（1972年7月27日）
「新 木枯し紋次郎」
第7話「四度渡った泪橋」（1977年11月16日） - 藤兵衛
第25話「生国は地獄にござんす」（1978年3月22日） - 弥助
「疾風同心」
第9話「狙われたドジな奴」（1978年11月15日）
第17話「お囃子お新」（1979年1月10日） - かげろうの粂
最終話「翔べ暴れん坊同心」（1979年3月14日） - 番太
「八丁堀あばれ軍団」第4話（1979年4月11日） - 番太
「日本名作怪談劇場」第3話（1979年7月4日） - 茂助
斬り捨て御免!シリーズ
「斬り捨て御免! 第1シリーズ」第1話（1980年4月9日）
「斬り捨て御免! 第3シリーズ」
第2話「大奥を濡らす魔性の血」（1982年6月16日）
第14話「生き地獄 女悪鬼の棲む館」（1982年9月8日）
「お命頂戴!」第12話（1981年12月23日）
「眠狂四郎無頼控」第4話（1983年4月27日）
「隠密・奥の細道」第16話（1989年1月20日）
12時間超ワイドドラマ「宮本武蔵」（1990年1月2日）
「大江戸捜査網」第6話（1990年11月16日） - 権三
「女無宿人 半身のお紺」第10話（1991年3月10日）
日本名作ドラマ「真実一路」後編（1993年9月27日））
あばれ八州御用旅シリーズ
「あばれ八州御用旅 第3シリーズ」第7話（1992年8月28日） - 勘八
「あばれ八州御用旅 第4シリーズ」第3話（1994年4月22日） - 長次
出演 > 特撮

「白獅子仮面」第5話 - 最終話（1973年5月2日 - 6月27日、日本テレビ） - ナレーター
出演 > CM

金蛇精
KDDI（2000年）
藤井久隆

| Hisataka FUJII> 基本情報 |
| --- | --- |
名前:  藤井 久隆
生年月日:   (1950-02-26) 1950年2月26日（74歳）
身長:  168 cm (5 ft 6 in)
体重:  62 kg (137 lb)
国籍:   日本
出身地:  福岡県
経歴
テンプレートを表示
藤井 久隆（ふじい ひさたか、1950年2月26日 - ）は、福岡県出身のプロゴルファー。
父は藤井義将。
娘の藤井千夏は現役の女子プロゴルファー 。
来歴

西南学院高等学校出身。
5歳からゴルフを始め、1975年にプロ入りする。
霞ヶ関カンツリー倶楽部に所属していた1971年には父・義将が日本オープンを制し、試合後にプロ仲間が帝国ホテルで祝勝会をするため、息子の久隆も呼ばれて駆け付けたが、当の藤井本人は「疲れたから」という理由で九州に帰ってしまった。
1979年の九州オープンでは秋富由利夫・杉田勇・鈴木規夫に次ぐと同時に上田鉄弘と並んでの5位タイに入った。
1980年の阿蘇ナショナルパークオープンでは初日を秋富・内田繁・草壁政治・鷹巣南雄と並んでの首位タイでスタートし、最終日には内田・田中文雄と並んでの4位タイに入った。
1986年の全日空オープンでは初日を中嶋常幸・青木功・菊地勝司・尾崎直道・石井裕士・渡辺司と並んでの5位タイでスタートし、2日目には内田と並んでの5位タイに留まり、3日目も内田と並んで6位タイと健闘。
1989年にはアコムダブルスで友利勝良とペアを組み、好天に恵まれた初日に67、2日目には63をマークし、飯合肇&佐野修一ペア、バリー・レーン&ピーター・ベイカー（イングランド）ペアと並んでの3位タイに着けた。
1993年のアコムインターナショナルを最後にレギュラーツアーから引退し、義将が設計したパサージュ琴海アイランドゴルフクラブ支配人 を経て、現在は古巣・麻生飯塚ゴルフ倶楽部支配人。
2009年には日本プロスポーツ大賞功労賞を受賞。
アメンエムハト6世

| アメンエムハト6世 |
| --- | --- |
 Amenemhat VI
 アメンエムハト6世のカルトゥーシュが記された奉納台
古代エジプト ファラオ
統治期間:  紀元前1788年頃 - 紀元前1785年頃，エジプト第13王朝
前王:  イウフニ
次王:  ネブウニ
  ファラオ名 (五重称号)           即位名: セアンクイブラー     誕生名: アメニ・アンテフ・アメンエムハト    
子息:  レニセネブ
父:  アンテフ?
テンプレートを表示
アメンエムハト6世（Amenemhat VI, 在位：紀元前1788年頃 - 紀元前1785年頃）は、古代エジプト第13王朝の第7代または8代ファラオ（王）
概要

即位名はセアンクイブラー。トリノ王名表の第6欄10行目に記されている。また、カルナック王名表の37番目にも名前が載っている。エル＝マハミドとエル＝クィブリからそれぞれ名前の刻まれた円柱が発見されており、カルナックやアビドスで見つかった石碑からもカルトゥーシュが確認されている。名前が刻まれた遺物の分布状況から、ヌビアまでを支配下に置いていた可能性が高い。
アメンエムハト6世の誕生名はアメニ・アンテフ・アメンエムハトという。Ryholtを中心とする研究者たちはこれを、王個人の名前に、父親や祖父の個人名を組み合わせたものと解釈している。その裏付けとなる証拠として、第13王朝時代の王の息子アンテフという人物の名前が記されたスカラベ印章が発見されている。このアンテフがアメンエムハト6世の父親だとすれば、その父である王の名前はアメニ、すなわちアメンエムハト5世である可能性が高い。彼以外にも、第13王朝の王たちには二つ以上の個人名で構成される誕生名を名乗っている者が多く、これを手掛かりに用いた王統の復元が試みられている。例えば、同時代の王アメニ・ケマウはアメンエムハト5世の息子で後継者であったと考えられている。さらに、ケマウ・サホルネジヘルイトエフはケマウの息子でアメンエムハト5世の孫、すなわちアメンエムハト6世の従兄弟であったと考えられている。そして、サホルネジヘルイトエフの後継者で、アメンエムハト6世の前任者のイウフニも彼らの兄弟であった可能性がある。しかし、一人の人間が複数の名前を持つ例も多く見られることから、この復元法に異論を唱える学者も多く、完全に確定された説ではない。
芋川椋三玄関番の巻

| 芋川椋三玄関番の巻 |
| --- | --- |
監督:  下川凹天
製作:  下川凹天
製作会社:  天然色活動写真
配給:  天然色活動写真
公開:   1917年4月?
上映時間:  不明
製作国:   日本
言語:  日本語
製作費:  不明
興行収入:  不明
前作:  凸坊新畫帖 名案の失敗（1917年）
次作:  茶目坊新畫帖 蚤夫婦仕返しの巻（1917年）
テンプレートを表示
『芋川椋三玄関番の巻』（いもかわむくぞうげんかんばんのまき）とは1917年4月に公開されたとされる日本国産最初期のアニメーション映画である。資料によっては『芋川椋三玄関番之巻』となっている場合もある。
作者は下川凹天（しもかわ へこてん・おうてん）。
作品内容

資料はほとんど無い為、ストーリーの内容や本編時間など全く不明。フィルムは21世紀現在でも現存が確認されていない。
映画会社に渡り何度か上映されたが、動きが雑で作者の下川ですら満足出来る作品とはならなかったといわれている。[要出典]
芋川椋三（いもかわむくぞう）というのは当時下川が漫画家として書いていたキャラクターの一人であり、それを主人公にしたのは彼が描きやすかった為だと言われている。
動画の技法として黒板にチョークで一つずつ書き、手を動かす時は手の部分だけを移動させて描き、移動前の部分を消していくという方法を使ったという説と背景を印刷した白紙を使い、人物と重複するところを白絵具で塗りつぶすという方法を使ったという説があるが、現在フィルム・写真などの記録が一切残っていない為、詳しい技法及び内容は不明である。ただし伝聞資料などによると、主人公・芋川椋三を中心とする、武骨ながらもユーモラスなものだったといわれている。
日本初であることに関しての議論

本作品は劇場で公開された日本制作のアニメ映画としては最も古いものであると言われてきたが、確実な証拠は発見されていない。日本初とされてきたのは以下の2つの理由による。
雑誌「キネマ・レコード」の1917年7月号の記事「和製カートン、コメディを見る」において、天活が最初の作品をキネマ倶楽部にて1917年1月に上場（公開）したという記述があること
雑誌「映画評論」1934年7月号に掲載された下川凹天の回想記事「日本最初の漫畫映畫製作の思ひ出」において、最初に制作した作品が『芋川椋三玄関番の巻』であると述べていること
しかし、当時の雑誌に掲載されている1917年1月の劇場上映作品リストに本作品の名前は存在しないこと、作品そのものについての資料が残っていないことなどから曖昧なものとなっている。
ただ、下川凹天の『凸坊新畫帖 名案の失敗』（1917年2月公開）が「第二次線畫トリツク（= 2つ目のアニメ作品）」とする記事が当時の雑誌に残っているため、少なくともそれ以前には最初のアニメ作品が上映されていただろうことは推測される。
2013年6月に公開された研究メモでは、
雑誌「キネマ・レコード」の1917年5月号の「フイルム見物 四月の巻」という4月に著者が劇場を回って見た作品を紹介する記事において、キネマ倶楽部で上映された「芋川椋三 玄關番の巻」が「天活第三次の線畫トリツクだ」とする記述がある
1934年の下川凹天の回想記事には、作品制作当時に月刊の映画雑誌が1つしかないと記述するなど事実誤認が見られる
などの理由から『芋川椋三玄関番の巻』は少なくとも1917年1月に公開された作品ではなく（つまり日本初の劇場公開作品ではない）、最新の研究から1月に上映された国産初のアニメ作品は『凸坊新畫帖 芋助猪狩の巻』と推測されている。そして、『芋川椋三玄関番の巻』は時期が近いことから1917年4月28日に公開された『茶目坊新畫帖 蚤夫婦仕返しの巻』と同じ作品であるとする指摘もある。
また、本作品を最初の作品としながらも、『凸坊新畫帖 名案の失敗』を最初の作品とする可能性を指摘している書籍もある。
なお、本作品より10年前の明治末期に制作された可能性のあるアニメーションフィルム『活動写真』が発見されているため、日本最古の国産アニメーションという場合には1917年の本作品は該当しない。ただし、このフィルムは個人観賞用の物とみられ、3秒程度しかない。
製作の背景

海外より輸入されたアニメーション映画に刺激を受けた日本の映画会社はその研究に乗り出し、1916年、天活こと天然色活動写真株式会社は漫画家の下川凹夫を迎え入れて研究を開始する。また、独自にアニメーションの製作を目指していた洋画家の北山清太郎は日活向島撮影所に1917年1月に参加し、アニメ製作を開始する。また、それらの動きを察知したと思われる小林商会は、1917年2月まで新聞で漫画を描いていた漫画家の幸内純一を迎え入れる。なお、下川と幸内はともに日本近代漫画の父である北澤楽天の弟子である。
この3社による競争となったが、1917年1月、天活が下川凹天の作品を公開し、それが国産アニメ映画の第1号となった。下川は続いて3作品ほど公開。そして、同年5月20日に、日活は北山清太郎の『猿蟹合戦』を公開。小林商会は同年6月30日に幸内純一の『塙凹内名刀（新刀）之巻（なまくら刀）』を公開した。
スタッフ

監督・演出・作画 ‐ 下川凹天
企画・製作・配給 ‐ 天然色活動写真
興行 ‐ キネマ倶楽部
計算複雑性理論

計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
「計算量」と「計算複雑性」はともに  に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。
概要

計算複雑性理論は計算可能関数の計算の複雑さを扱う。計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。これは、計算機の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、NPやPといった複雑性クラスに分類する。個々の計算問題を少ない計算資源で解くアルゴリズムを発見することはもちろん計算機科学の重要な課題だが、複雑性理論ではこれにとどまらず、計算問題が何らかの複雑性クラスに属すること、あるいは属しないことを証明したり、クラス間の階層構造を解明することも目標とする。
計算量 tC をもつ複雑性クラス C に 或る計算問題 X が属する とは、あるアルゴリズム A が存在して、問題 X が A により tC以下で解決されることを意味し、問題 X の複雑性の上界を与える。そして、よりよい上界を求めることは、問題 X をより少ない計算資源で解くアルゴリズムを発見する(あるいはその存在を示す)ことに他ならず、産業界において有意義である。また、ある計算問題 X が、ある複雑性クラス C に属しないとは、問題 X は、いかなるアルゴリズムをもってしても、計算量 tC 以下では解決できないことを意味し、問題 X の複雑性の下界を与える。計算問題の下界を示すことは、理論的意義を有するだけではなくて、暗号理論においては、ある暗号方式が計算量的に解読不能であることを示すことを意味し、実際的な価値がある。
現在の計算複雑性理論の最も重要な課題は、P≠NP予想の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要なオペレーションズリサーチの問題の多くがNPの部分クラスに属するNP完全問題であることが明らかになるにつれて重要性を増してきた。NP完全問題は、解が正しいかどうかは簡単に確かめられるが、正確な解を探す方法はスケーラブルではない問題である。NPクラスがPクラスより範囲が広いことが確定すると、それらの問題にはスケーラブルな解が存在しないことが確定する。このため、P≠NP予想の証明は重要とされているのである。
計算問題と計算量・複雑性

計算複雑性理論で扱う問題とは、ある一連の問いの集合があり、各問いは有限長の文字列で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、FACTORIZE問題とは「二進数で書かれた1つの整数について、その素因数を全部求めて返す」という問題である。問題に属する個別の問いをインスタンスと呼ぶ。例えば、「15 の素因数を求めよ」は FACTORIZE 問題のインスタンスである。
アルゴリズムの計算量（けいさんりょう）とは、計算機がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムのスケーラビリティを示す。形式的には計算機をチューリング機械やランダムアクセス機械（random access machine）などの計算モデルとして定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する関数として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視するO記法で書き表すことが多い。計算モデルとしては、チューリング機械や論理回路などがある。計算資源の量としては、チューリング機械における時間計算量（動作ステップ数）や空間計算量（テープ長）、また論理回路における素子数や深さなどがある。
時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。シンプルな例として、ある問題に対する解法が nビットの入力に対して、ある計算モデルで n2 ステップで動作する場合、時間計算量は n2 であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、O記法を使えば計算モデルによらず問題の時間計算量をO(n2) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を二分探索する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。
空間計算量は、同様の概念であり、アルゴリズムが必要とする記憶容量を意味する。例えば、紙とペンを使って計算を行う際に要する紙の枚数に相当する。空間計算量にもO記法が使われる。
計算モデルによっては、これらとは異なる計算量が使われることもあり、例えば回路計算量がある。これは問題の解法をブール論理による論理回路ゲートに置き換え、その回路の規模で計算量を現すものである。これは集積回路の設計などで利用される。
計算問題の複雑性（または計算量）とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。
決定問題

計算複雑性理論で扱う計算問題の多くは決定問題である。決定問題とは、答えが「はい」か「いいえ」になる問題を指す。
決定問題を主に扱うのは、任意の計算問題を何らかの決定問題に還元することが常に可能だからである。例えば、HAS-FACTOR を与えられた整数 n と k（どちらも二進数で与えるとする）について、n が k より小さい素因数をもつかどうかに答える決定問題とする。すると、計算問題 FACTORIZE（素因数分解）の解法は、HAS-FACTOR を使って実現でき、その際に追加の資源はそれほど要しない。具体的には k について二分探索を行い、n の最小素因数を探索し、その値で n を割る。そして、商について再び同じ作業を繰り返していけばよい。このことは、HAS-FACTOR の解法をある計算資源量で実現できるか否かが分れば、FACTORIZE の解法についても分るということを意味する。
計算複雑性理論では、答えが「はい」かどうかを確認する問題と、答えが「いいえ」かどうかを確認する問題を区別する。「はい」と「いいえ」を逆転させた問題は、元の問題の補問題と呼ばれる。
例えば、決定問題 IS-PRIME（素数判定問題）は、入力が素数の場合に「はい」、そうでなければ「いいえ」を返す。一方、問題 IS-COMPOSITE は与えられた整数が素数でない（すなわち合成数である）ことを決定する。IS-PRIME が「はい」を返すなら、IS-COMPOSITE は「いいえ」を返す。逆も成り立つ。したがって IS-COMPOSITE は IS-PRIME の補問題であり、同様に IS-PRIME は IS-COMPOSITE の補問題である。
ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、IS-COMPOSITE問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、IS-PRIME問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラスNPとco-NPなどで重要となる。
計算複雑性理論の重要な成果の1つとして、ある難しい問題があったとき（それがいかに大量の時間資源や空間資源を要したとしても）、それよりさらに難しい問題が必ず存在するという事実がある。時間計算量については時間階層定理（英語版）によってこれが証明されている。同様に領域階層定理（英語版）も導かれる。
計算資源

計算複雑性理論は計算問題の難しさを様々な計算資源の観点で分析する。時間、空間、無作為性、反復性、その他のより直観的でない尺度などで必要とする計算資源量によって、同じ問題を説明する。複雑性クラスはある特定の計算資源をある特定の量つかって解くことができる全計算問題の集合である。
最も研究が進んでいる計算資源は決定性時間(DTIME) と決定性空間(DSPACE) である。これらの資源はそれぞれ、決定性のある計算機（例えば実在する普通の計算機）で問題を解くのに必要な「計算時間（演算回数）」と「記憶装置」の量に対応している。これらの資源の使用量を求めることは実用的な意味もあり、研究が進んでいるのである。
いくつかの計算問題は非現実的な量の資源を想定すれば、より容易に解析可能である。例えば、非決定性チューリング機械は、分岐して様々な可能性を同時にチェックできるという計算モデルである。したがって、非決定性チューリング機械はアルゴリズムを使って具体的に計算する作業とは全く関係ないが、その分岐によって分析したい計算モデルの大部分を捉える。このため非決定性時間は計算問題を分析するにあたって非常に重要な資源である。
計算複雑性理論では他にもいろいろな計算資源を考慮する。技術的には、複雑性尺度として計算資源量が扱われ、これに関してはブラムの公理で非常に一般的な定義が与えられている。
複雑性クラス

ある量の計算資源を使って解くことができるすべての計算問題の集合を複雑性クラスという。
複雑性クラス P は、チューリング機械で多項式時間で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である。
複雑性クラス NP は、非決定性チューリング機械で多項式時間で解ける決定問題の集合である。このクラスには効率的に解くことが望ましいとされる様々な問題が含まれている。例えば、充足可能性問題、ハミルトン閉路問題、頂点被覆問題などである。このクラスの全問題は、その解法を効率的に検証する方法があるという特徴を持つ。
多くの複雑性クラスは、それを表現するのに必要となる論理体系によって特徴付けられる。これは、記述計算量の概念と関係がある。
各クラスに対し、そのクラスの完全問題を考えることがある。クラスCの完全問題とはCに属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。
複雑性クラス > 主な複雑性クラス

L
NL
NC
P
NP（NP困難, NP完全）
co-NP
PSPACE
EXPTIME
BPP
BQP
未解決の問題 > P = NP 問題

→詳細は「P≠NP予想」を参照
NPがPと同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている。同じであった場合に都合が悪い影響として、暗号理論の多くがNPの困難さに依存しているため、Pと同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、オペレーションズリサーチにおける整数計画問題、物流合理化、生物学におけるタンパク質構造予測、純粋数学の定理を計算機で効率的に形式的に証明する可能性などがある。クレイ数学研究所は2000年に、この問題を最初に解いた人に100万ドルを支払うと発表した。
この問題を考えるにあたって重要となるのは、NP完全の概念である。NP完全な問題はNPの中では最もPから遠い問題ということになる。P = NPが証明されていないため、ある問題をNP完全と判明している問題に還元できるということは、その問題の多項式時間の解法が未知であることを示している。逆に、すべての NP問題はNP完全問題に還元できるため、NP完全問題の多項式時間の解法を発見すれば、P = NPが証明される。（一方、たとえP = NPが成立しても、NP困難な問題は多項式時間で解けるとは限らない。理由はNP困難のページを参照のこと）
未解決の問題 > NPにおける不完全問題

上の問題に関連して、NPクラスに属する問題でPクラスには属しないがNP完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、NP完全問題から多項式時間で還元できない問題ということである。このような問題のクラスをNP-intermediate（英語版）と呼び、候補としてグラフ同型問題や整数の因数分解、離散対数問題などがある。もしP ≠ NPが真ならば、そのような問題が存在することが証明されている。
未解決の問題 > NP = co-NP

co-NPクラスはNP問題の補問題の集合である（すなわち、「はい」と「いいえ」が逆転している問題）。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる。
イントラクタブル

→「組合せ爆発」も参照
理論上計算可能な問題であっても、実際に解くことができない問題をイントラクタブル (英: intractable, 手に負えない、処理しにくい) であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、EXPTIME完全な問題がある。NP が P と同じでなかった場合、NP完全な問題もイントラクタブルだということになる。
指数関数時間の解法がなぜ実際には使えないかを考えるため、2n 回の操作を必要とする問題を考える（n は入力のサイズである）。比較的小さな入力数 n = 100 のときについて、1秒間に 1010（10 ギガ）回命令を実行できる計算機を想定すると、その問題を解くには約 4 × 1012 年かかる。これは現在の宇宙の年齢よりも長い。
主な研究者

マヌエル・ブラム: ブラムの公理に基づいた公理的複雑性理論を構築した
スティーブン・クック
ユリス・ハルトマニス
リチャード・カープ
アディ・シャミア
リチャード・スターンズ
アンドリュー・チーチー・ヤオ
レスリー・ヴァリアント
Leonid Levin（英語版）
ナイトメア (バンド)

| ナイトメア |
| --- | --- |
 
基本情報
出身地:   日本・宮城県仙台市
ジャンル:  ロック ハードロック ヘヴィメタル ゴシック・ロック ファンク・メタル ハードコア・パンク
活動期間:  2000年 - 2016年 2020年 -
レーベル:   SPEED DISK/XXX RECORDS  （2001年 - 2003年）  日本クラウン  （2003年 - 2006年）  バップ  （2006年 - 2011年）  HPQ  （2011年 - 2016年）  littleHEARTS.Music  （2020年 - ） 
事務所:   SPEED DISK  （2001年 - 2003年）  C-block  （2003年 - ） 
共同作業者:  仙台貨物
公式サイト:  ナイトメア：Nightmare Official Site

メンバー:   YOMI（ボーカル）  柩（ギター）  咲人（ギター）  Ni〜ya（ベース）  RUKA（ドラムス） 
| NIGHTMARE> YouTube |
| --- | --- |
チャンネル:   NIGHTMARE OFFICIAL CHANNEL 
活動期間:  2020年 -
ジャンル:  音楽
登録者数:  約4.55万人
総再生回数:  約198万回
チャンネル登録者数・総再生回数は 2024年1月9日時点。
テンプレートを表示
ナイトメア (NIGHTMARE) は、日本のヴィジュアル系ロックバンド。略称はメア。
メンバー

YOMI：（ヨミ／黄泉、 (1981-07-14) 1981年7月14日（43歳） - ）ボーカル担当。バングルカラーはイエロー。
柩 ：（ヒツギ、 (1982-03-05 ) 1982年3月5日（42歳） - ）
ギター担当、バングルカラーはレッド。
咲人 ：（サキト、 (1981-06-29 ) 1981年6月29日（43歳） - ）
ギター担当、バングルカラーはブラック。
Ni〜ya ：（ニーヤ／新弥、 (1981-06-23 ) 1981年6月23日（43歳） - ）
ベース担当、バングルカラーはブルー。
RUKA （ルカ／瑠樺、 (1979-06-09 ) 1979年6月9日（45歳） - ）
ドラム担当、リーダー、バングルカラーはピンク。
概要

バンド名の由来は、英和辞書から響きが良い物を何百個も拾い、それを消去法で30個ほどに削り、その意味を全部調べ、「ヴィジュアル系バンドだし、化粧もするし綺麗なバンドにはなりたくない」という意見から、悪夢=Nightmareが良いのではということになり決定した。
メンバー全員がX JAPANやLUNA SEAから影響を受けていると公言しており、作曲は主にコンポーザーである咲人、RUKAが担当。作詞は咲人、RUKA、黄泉に加え、柩もいくつか提供している。歌詞は、社会批判的なものから悲恋歌まで幅広いが、痛みや傷、喪失感や虚無感を捉えた内容が多い。また、「わすれな草」や「M-aria」などRUKAが作詞した曲のいくつかは、彼のかつての実話が描かれている。楽曲においてはマイナーメロディの曲が多い。代表的な曲としてはジャイアニズムシリーズがあり、曲のタイトルとしてジャイアニズム痛＝ジャイアニズム2、ジャイアニズム惨＝ジャイアニズム3など数字を当てはめている。なおジャイアニズム1は＝自傷(少年テロリスト)の事であり、また4作目も欠番扱いだったが「YOMIが歌えない」という理由で正式に音源化されなかったものの、ベスト・アルバム『GIANIZM』で正式に音源化されている。
また、ファンクラブ限定ライヴやファンクラブ旅行内では、バンド内での特別セッション：カッペロ（YOMI&咲人）、M魔王withHOIZ（柩&Ni～ya&RUKA）などのユニットも組まれている。
作品

詳細は各作品の項目を参照。
作品 > シングル

インディーズ
|   | 発売日 | タイトル | 備考 |
| --- | --- | --- | --- |
| 1st | 不明 | Vice | ライブ会場限定販売 |
| 2nd | 2001年10月21日(1st press) 2001年11月11日(2nd press) | 犯行期 | 1st、2nd共に1000枚限定 |
| 3rd | 2002年2月21日 | 自由奔放天真爛漫 | 1st2000枚、2nd3000枚限定 2nd pressにのみボーナストラック収録 |

メジャー
|   | 発売日 | タイトル | 備考 |
| --- | --- | --- | --- |
| 1st | 2003年8月21日 | - Believe - | オリコン週間ランキング初登場24位 |
| 2nd | 2003年11月21日 | 茜/HATE/Over | オリコン週間ランキング初登場25位 「Over」：テレビ東京系テレビアニメ「コロッケ!」EDテーマ |
| 3rd | 2004年4月21日 | Varuna | オリコン週間ランキング初登場29位 |
| 4th | 2004年7月22日 | 東京傷年 | オリコン週間ランキング初登場21位 |
| 5th | 2004年10月21日 | シアン | オリコン週間ランキング初登場22位 |
| 6th | 2005年4月1日 | 時分ノ花 | オリコン週間ランキング初登場21位 |
| 7th | 2005年8月10日 | Яaven Loud speeeaker | オリコン週間ランキング初登場23位 |
| 8th | 2005年12月7日 | livEVIL | オリコン週間ランキング初登場29位 |
| 9th | 2006年10月18日 | the WORLD/アルミナ | DEATH NOTE OPテーマ/EDテーマ |
| 10th | 2007年6月6日 | レゾンデートル | CLAYMORE OPテーマ |
| ライブ会場限定 | 2007年9月28日 | Star[K]night | ライブ「極東シンフォニー」にて限定販売 |
| 11th | 2007年10月3日 | このは | オリコン週間ランキング初登場4位 |
| 12th | 2007年11月7日 | DIRTY | 魔人探偵脳噛ネウロ OPテーマ |
| 13th | 2008年9月17日 | Lost in Blue | 魍魎の匣 OPテーマ |
| 14th | 2008年12月3日 | NAKED LOVE | 魍魎の匣 EDテーマ |
| 15th | 2009年9月22日 | Rem_ | オリコン週間ランキング初登場3位 |
| 16th | 2010年6月23日 | a:FANTASIA | オリコン週間ランキング初登場5位 |
| 17th | 2011年5月18日 | VERMILION. | エイベックス移籍第1弾シングル オリコン週間ランキング初登場6位 |
| 18th | 2011年9月7日 | SLEEPER | ジェムケリーCMソング オリコン週間ランキング初登場7位 |
| 19th | 2012年2月29日 | mimic | オリコン週間ランキング初登場9位 |
| 20th | 2012年11月28日 | Deus ex machina | オリコン週間ランキング初登場11位 |
| 21st | 2013年8月21日 | Dizzy | オリコン週間ランキング初登場13位 |
| 22nd | 2014年1月8日 | リライト | オリコン週間ランキング初登場2位 |
| 23rd | 2014年6月25日 | TABOO | 映画『奴隷区 僕と23人の奴隷』オープニングテーマ オリコン週間ランキング初登場6位 |
| 24th | 2015年1月7日 | blur | オリコン週間ランキング初登場8位 |
| 25th | 2015年11月9日 | 落園 | オリコン週間ランキング初登場15位 |
| 26th | 2016年3月23日 | Awakening. | オリコン週間ランキング初登場10位 |
| 27th | 2020年10月7日 | ink | テレビ朝日系『BREAK OUT』2020年10月度オープニング・トラック 「Fear」：フジテレビ系「Tune」11月度マンスリーアーティスト オリコン週間ランキング初登場8位 |
| 28th | 2021年3月3日 | cry for the moon | 日本テレビ系『バズリズム02』2021年3月オープニングテーマ オリコン週間ランキング初登場3位 |
| 29th | 2021年11月17日 | Sinners | テレビ東京系『デュエル・マスターズ キング!』オープニングテーマ オリコン週間ランキング初登場13位 |
| 30th | 2022年11月16日 | With | アニメ「最後の召喚師 -The Last Summoner-」オープニングテーマ オリコン週間ランキング初登場13位 |
| 31st | 2023年3月29日 | FAREWELL | 日本テレビ系『バズリズム02』2023年4月エンディングテーマ オリコン週間ランキング初登場13位 |
| 32nd | 2023年11月8日 | Rebel |  |
作品 > アルバム

インディーズ
|   | 発売日 | タイトル | 備考 |
| --- | --- | --- | --- |
| 1st | 2002年11月22日 | アウトロー | 5000枚限定　オリコン週間ランキング初登場113位 |

メジャー
|   | 発売日 | タイトル | 備考 |
| --- | --- | --- | --- |
| 1st | 2003年12月25日 | Ultimate Circus | 　オリコン週間ランキング初登場115位 |
| 2nd | 2004年12月21日 | リヴィド | 　オリコン週間ランキング初登場29位 |
| 3rd | 2006年2月26日 | anima | 　オリコン週間ランキング初登場12位 |
| 4th | 2007年2月28日 | the WORLD Ruler | 　オリコン週間ランキング初登場6位 |
| 5th | 2008年5月21日 | Killer Show | 　オリコン週間ランキング初登場5位 |
| 6th | 2009年5月13日 | majestical parade | 　オリコン週間ランキング初登場3位 |
| 7th | 2011年11月23日 | NIGHTMARE | 　オリコン週間ランキング初登場10位 |
| 8th | 2013年1月30日 | SCUMS | 　オリコン週間ランキング初登場8位 |
| 9th | 2014年3月19日 | TO BE OR NOT TO BE | 　オリコン週間ランキング初登場11位 |
| 10th | 2015年3月25日 | CARPE DIEM | 　オリコン週間ランキング初登場7位 |
| 11th | 2022年3月16日 | NOX:LUX | 　オリコン週間ランキング初登場15位 |
作品 > ベスト・アルバム

|   | 発売日 | タイトル | 備考 |
| --- | --- | --- | --- |
| 1st | 2003年4月21日 2006年6月21日(再発) | ジャイアニズム〜お前の物は俺の物〜 | 再発時には2作品がセットになったものが発売された。 |
| 2nd | 2003年5月21日 2006年6月21日(再発) | ジャイアニズム〜俺の物は俺の物〜 | 再発時には2作品がセットになったものが発売された。 |
| 3rd | 2006年5月10日 | ジャイアニズム 〜ナイトメアのくせに生意気だぞ〜 |  |
| 4th | 2008年1月30日 | ナイトメア 2003-2005 シングル・コレクション |  |
| 5th | 2010年1月1日 | GIANIZM |  |
| 6th | 2010年10月20日 | Historical 〜The highest NIGHTMARE〜 |  |
| 7th | 2015年11月25日 | best tracks 2011-2015 ［beást］ | ベスト・アルバム3部作第1弾。 |
| 8th | 2016年1月6日 | best tracks 2006-2010 ［vapor］ | ベスト・アルバム3部作第2弾。 |
| 9th | 2016年3月23日 | best tracks 2000-2005 ［ćlowns］ | ベスト・アルバム3部作第3弾。 |
| 10th | 2020年3月6日 | 20th Anniversary NIGHTMARE PERSONAL BEST 柩 Edition |  |
| 11th | 2020年6月9日 | 20th Anniversary NIGHTMARE PERSONAL BEST RUKA Edition |  |
| 12th | 2020年6月23日 | 20th Anniversary NIGHTMARE PERSONAL BEST Ni〜ya Edition |  |
| 13th | 2020年6月29日 | 20th Anniversary NIGHTMARE PERSONAL BEST 咲人 Edition |  |
| 14th | 2020年7月14日 | 20th Anniversary NIGHTMARE PERSONAL BEST YOMI Edition |  |
作品 > ライブ・アルバム

|   | 発売日 | タイトル | 備考 |
| --- | --- | --- | --- |
| 1st | 2008年2月27日 | 極東シンフォニー 〜the Five Stars Night〜 @BUDOKAN | 完全予約限定盤、武道館衣装ピース付レプリカSTAFFパスランダム封入。 |
| 2nd | 2010年8月25日 | NIGHTMARE 10th anniversary special act vol.1 GIANIZM 〜天魔覆滅〜 | トレーディングカード封入、10周年スペシャルクーポン券付。 |
| 3rd | 2012年6月6日 | NIGHTMARE TOUR 2011-2012 Nightmarish reality TOUR FINAL ＠ NIPPONBUDOKAN |  |
| 4th | 2014年11月19日 | 「NIGHTMARE TOUR 2014 TO BE OR NOT TO BE：That is the Question.」TOUR FINAL @ 東京国際フォーラムホールA |  |