• 研究課題をさがす
  • 研究者をさがす
  • KAKENの使い方
  1. 前のページに戻る

長尾 篤樹  NAGAO Atsuki

ORCIDORCID連携する *注記
研究者番号 20802622
その他のID
所属 (現在) 2025年度: お茶の水女子大学, 基幹研究院, 准教授
所属 (過去の研究課題情報に基づく) *注記 2022年度 – 2024年度: お茶の水女子大学, 基幹研究院, 講師
2018年度 – 2021年度: お茶の水女子大学, 基幹研究院, 助教
審査区分/研究分野
研究代表者
小区分60010:情報学基礎論関連
研究代表者以外
小区分60010:情報学基礎論関連 / 合同審査対象区分:小区分60010:情報学基礎論関連、小区分60020:数理情報学関連 / 小区分60020:数理情報学関連
キーワード
研究代表者
計算量理論 / 計算量クラスの分離 / 分岐プログラム / 対数領域計算モデル / Read-k-time / Sub-SAT / 厳密アルゴリズム / アルゴリズム / 充足可能性問題 / 一回読み制限 / 木構造関数値評価問題 / 領域計算量 … もっと見る
研究代表者以外
… もっと見る 充足可能性問題 / パラメータ化アルゴリズム / 計算複雑性 / 組合せ最適化問題 / 解の唯一化 / SATアルゴリズム / 回路計算量 / 下界証明 / 二元体上の連立線形方程式 / 多数決関数 / 定数段数回路 / 解空間の連結性判定 / k-Horn式 / 3段回路 / Depth-3 Circuit / Branching Program / Bounded Width / Satisfiability / 計算量理論 / 指数時間仮説 / 幅限定 / 分岐プログラム / 置換分岐プログラム / 幅限定分岐プログラム / 充足可能性判定 / 厳密アルゴリズム / 強指数時間仮説 隠す
  • 研究課題

    (5件)
  • 研究成果

    (3件)
  • 共同研究者

    (2人)
  •  組合せ最適化問題に対する解の唯一化における計算複雑さの研究

    • 研究代表者
      脊戸 和寿
    • 研究期間 (年度)
      2024 – 2027
    • 研究種目
      基盤研究(B)
    • 審査区分
      小区分60010:情報学基礎論関連
      小区分60020:数理情報学関連
      合同審査対象区分:小区分60010:情報学基礎論関連、小区分60020:数理情報学関連
    • 研究機関
      北海道大学
  •  対数領域計算モデルの限界を示す関数の模索研究代表者

    • 研究代表者
      長尾 篤樹
    • 研究期間 (年度)
      2023 – 2026
    • 研究種目
      基盤研究(C)
    • 審査区分
      小区分60010:情報学基礎論関連
    • 研究機関
      お茶の水女子大学
  •  定数段数回路における計算限界導出技法の研究

    • 研究代表者
      脊戸 和寿
    • 研究期間 (年度)
      2021 – 2023
    • 研究種目
      基盤研究(C)
    • 審査区分
      小区分60010:情報学基礎論関連
    • 研究機関
      北海道大学
  •  対数領域計算モデルのメモリアクセス回数による能力の比較研究代表者

    • 研究代表者
      長尾 篤樹
    • 研究期間 (年度)
      2020 – 2023
    • 研究種目
      若手研究
    • 審査区分
      小区分60010:情報学基礎論関連
    • 研究機関
      お茶の水女子大学
  •  強指数時間仮説の反証にむけた研究

    • 研究代表者
      脊戸 和寿
    • 研究期間 (年度)
      2018 – 2021
    • 研究種目
      基盤研究(C)
    • 審査区分
      小区分60010:情報学基礎論関連
    • 研究機関
      北海道大学
      成蹊大学

すべて 2022 2020

すべて 雑誌論文 学会発表

  • [雑誌論文] A Satisfiability Algorithm for Deterministic Width-2 Branching Programs2022

    • 著者名/発表者名
      Tomu MAKITA, Atsuki NAGAO, Tatsuki OKADA, Kazuhisa SETO, Junichi TERUYAMA
    • 雑誌名

      IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

      巻: E105.A 号: 9 ページ: 1298-1308

    • DOI

      10.1587/transfun.2021EAP1120

    • ISSN
      0916-8508, 1745-1337
    • 年月日
      2022-09-01
    • 言語
      英語
    • 査読あり / オープンアクセス
    • データソース
      KAKENHI-PROJECT-18K11170, KAKENHI-PUBLICLY-21H05839, KAKENHI-PROJECT-21K11743, KAKENHI-PROJECT-20K19741, KAKENHI-PROJECT-22K11910, KAKENHI-PROJECT-18K18003, KAKENHI-PLANNED-20H05794
  • [雑誌論文] Satisfiability Algorithm for Syntactic Read-k-times Branching Programs2020

    • 著者名/発表者名
      Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama
    • 雑誌名

      Theory of Computing Systems

      巻: 64 号: 8 ページ: 1392-1407

    • DOI

      10.1007/s00224-020-09996-3

    • 査読あり / オープンアクセス
    • データソース
      KAKENHI-PROJECT-18K11170, KAKENHI-PROJECT-18K18003, KAKENHI-PROJECT-20K19741
  • [学会発表] A Moderately Exponential Time Satisfiability Algorithm for Linear-Sized Deterministic Width-2 Branching Programs2022

    • 著者名/発表者名
      Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, and Junichi Teruyama
    • 学会等名
      電子情報通信学会コンピュテーション研究会
    • データソース
      KAKENHI-PROJECT-21K11743
  • 1.  脊戸 和寿 (20584056)
    共同の研究課題数: 3件
    共同の研究成果数: 2件
  • 2.  小野 廣隆 (00346826)
    共同の研究課題数: 1件
    共同の研究成果数: 0件

URL: 

この研究者とORCID iDの連携を行いますか?
※ この処理は、研究者本人だけが実行できます。

Are you sure that you want to link your ORCID iD to your KAKEN Researcher profile?
* This action can be performed only by the researcher himself/herself who is listed on the KAKEN Researcher’s page. Are you sure that this KAKEN Researcher’s page is your page?

サービス概要 検索マニュアル よくある質問 お知らせ 利用規程 科研費による研究の帰属

Powered by NII kakenhi