The complexity class \({\exists {\mathbb {R}}}\) , standing for the complexity of deciding the existential first order theory of the reals as real closed field in the Turing model, has raised considerable interest in recent years. It is well known that \(\textrm{NP}\subseteq {\exists {\mathbb {R}}}\subseteq \textrm{PSPACE}.\) In their compendium [23], Schaefer, Cardinal, and Miltzow give a comprehensive presentation of results together with a rich collection of open problems. Here, we answer some of them dealing with structural issues of \({\exists {\mathbb {R}}}\) as a complexity class. We show analogues of the classical results of Baker, Gill, and Solovay finding oracles which do and do not separate NP from \({\exists {\mathbb {R}}}\) , of Ladner’s theorem showing the existence of problems in \({\exists {\mathbb {R}}}\setminus \textrm{NP}\) not being complete for \({\exists {\mathbb {R}}}\) (in case the two classes are different), as well as a characterization of \({\exists {\mathbb {R}}}\) by means of descriptive complexity.

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

Some Structural Complexity Results for  \(\exists {\mathbb {R}}\)

  • Klaus Meer,
  • Adrian Wurm

摘要

The complexity class \({\exists {\mathbb {R}}}\) , standing for the complexity of deciding the existential first order theory of the reals as real closed field in the Turing model, has raised considerable interest in recent years. It is well known that \(\textrm{NP}\subseteq {\exists {\mathbb {R}}}\subseteq \textrm{PSPACE}.\) In their compendium [23], Schaefer, Cardinal, and Miltzow give a comprehensive presentation of results together with a rich collection of open problems. Here, we answer some of them dealing with structural issues of \({\exists {\mathbb {R}}}\) as a complexity class. We show analogues of the classical results of Baker, Gill, and Solovay finding oracles which do and do not separate NP from \({\exists {\mathbb {R}}}\) , of Ladner’s theorem showing the existence of problems in \({\exists {\mathbb {R}}}\setminus \textrm{NP}\) not being complete for \({\exists {\mathbb {R}}}\) (in case the two classes are different), as well as a characterization of \({\exists {\mathbb {R}}}\) by means of descriptive complexity.