Scholarlink

Some general transfer principles for unit cost complexity problems are proved. As an application, we show that for infinite abelian groups \(\Sigma ^2 \cap \Pi ^2 \neq \Sigma ^1 \cup \Pi ^1\) . This has been shown for the group of real numbers by Herve Fournier and Pascal Koiran using the problem Twenty Questions. As this problem is not appropriate for infinite abelian groups in general, it was replaced here by Null-sack.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The Path-bifurcation Hierarchy Does Not Collapse to \(\Sigma ^1\) in Infinite Abelian Groups

  • 章节

  • 发表日期：

    2025年

查看全文
  • Mihai Prunescu

摘要

Some general transfer principles for unit cost complexity problems are proved. As an application, we show that for infinite abelian groups \(\Sigma ^2 \cap \Pi ^2 \neq \Sigma ^1 \cup \Pi ^1\) . This has been shown for the group of real numbers by Herve Fournier and Pascal Koiran using the problem Twenty Questions. As this problem is not appropriate for infinite abelian groups in general, it was replaced here by Null-sack.