論文の概要: Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students

• arxiv url: http://arxiv.org/abs/2608.12976v1
• Date: Thu, 13 Aug 2026 08:56:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-17 13:59:16.222438
• Title: Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students
• Title（参考訳）: フォーチュン・バウンティ : トリミング・ツリーによるテイミング・コンプレシティー--入門生に適した高度な複雑度における問題解決体験-
• Authors: Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan,
• Abstract要約: 本稿では,大学院生のCS1/CS2シーケンスを完了した学生に対して,Fortuneの定理を証明するための課題について述べる。
• 参考スコア（独自算出の注目度）: 3.119884465012285
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.
• Abstract（参考訳）: 本稿では,大学院生のCS1/CS2シーケンスを完了した学生に対して,Fortuneの定理を証明するための課題について述べる。 (Fortune's Theorem は、ブール充足可能性問題の補足がスパース集合に還元された場合、ブール充足性問題は多項式時間計算可能であると仮定している。この代入は、生徒が以前にブール充足性問題、多項式時間縮小、スパース集合を見たと仮定していない。むしろ、その代入の中でそれらを教えている。注意:複雑性理論の技術的語彙に言い換えると、Fortune's Theorem は、スパース集合は P=NP でない限り coNP-hard ではない。Fortune's Theorem は、硬度と密度の関係の理解において大きな進歩であった。)。 課題ハンドアウトは、インストラクターがこれを変更できるが、学生がクラスセッション全体のためにクラス内のチームで割り当てを開始させ、同じチームでそれをテイクホームの割り当てとして終了させ、次のクラスセッションの前にそれを手渡すようにフレーム化されている。 学生グループは、この課題において、部分的にも完全にも、しばしば成功していることがわかった。 これは学生にとって大きな意味を持つ:彼らは、それが最初に入手された時に、複雑性理論研究のトップジャーナルの会場として間違いなく現れた進歩を成し遂げた、と彼らは見ている。 このことは、彼らが与えられた課題に真に適用するときに、実質的な問題解決スキル(基本的には研究スキル)を持っているという自信を与えます。

関連論文リスト

• Ineq-Comp: Benchmarking Human-Intuitive Compositional Reasoning in Automated Theorem Proving on Inequalities [46.111273938884295]
  本研究では,AM/GMのような既知の不等式を適用することにより,与えられた問題が単純化されることを認識するプロバーの能力について検討する。 これらの問題は人間にとって容易なままだが、Goedel、書き直し、Kimina-7Bを含むほとんどのプローバーは、かなり苦労している。 我々の結果は、現在のAIプロデューサの行動と人間の直感の間に持続的なギャップを露呈する。
  論文  参考訳（メタデータ） (2025-05-19T03:56:05Z)
• Probabilistic and Causal Satisfiability: Constraining the Model [0.49399484784577985]
  確率論的および因果推論における充足可能性問題の複雑性について検討する。 基本的な用語は、原子事象に対する命題公式の確率である。 モデルに2つの新たな次元を加えることで、この作業線を拡張します。
  論文  参考訳（メタデータ） (2025-04-28T16:14:06Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化 正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。 新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
  論文  参考訳（メタデータ） (2025-04-02T17:45:58Z)
• Direct sum theorems beyond query complexity [0.0]
  コンピュータサイエンスの根本的な疑問は、$n$インスタンスを同時に解決するよりも、独立して解決することが難しいか、ということです。 本稿では,古典的/量子的クエリ複雑性,機械学習のためのPAC学習,統計的推定理論などを拡張する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-28T06:53:29Z)
• TheoremQA: A Theorem-driven Question Answering dataset [100.39878559382694]
  GPT-4のこれらの問題を解決する能力は非並列であり、Program-of-Thoughts Promptingの精度は51%である。 TheoremQAは、350の定理をカバーする800の高品質な質問を含むドメインの専門家によってキュレートされる。
  論文  参考訳（メタデータ） (2023-05-21T17:51:35Z)
• On Theoretical Complexity and Boolean Satisfiability [0.0]
  この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。 次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。 最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
  論文  参考訳（メタデータ） (2021-12-22T10:13:34Z)
• Hierarchical Bayesian Bandits [51.67132887113412]
  このクラスでは,任意の問題に適用可能な自然階層型トンプソンサンプリングアルゴリズム (hierTS) を解析する。 私たちの後悔の限界は、タスクが順次あるいは並列に解決された場合を含む、そのような問題の多くの事例に当てはまる。 実験により、階層構造はタスク間の知識共有に役立つことが示された。
  論文  参考訳（メタデータ） (2021-11-12T20:33:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。