Nondeterministic bounded query reducibilities

DOI10.1016/0168-0072(89)90010-9MaRDI QIDQ1120564zbMATH OpenOpenAlexFDO

Authors Richard Beigel, William Gasarch, James C. jun. Owings

Publication date 1989

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(89)90010-9

zbMATH Keywords

bounded number of calls to the oraclenondeterministic oracle machinesobjective setsubjective settruth-table degreeTuring degree

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Review text

The behavior of nondeterministic oracle machines with a bounded number of calls to the oracle is considered. For any set A of natural numbers we define \(F^ A_ n(x_ 1,...,x_ n)=<\chi_ A(x_ 1),...,\chi_ A(x_ n)>\). Denote by FQ(n,B) (NFQ(n,B)) the class of functions computable by a deterministic (nondeterministic) machine with the oracle B and with at most n calls to B for each (branch of its) computation. A set a is called n-subjective if \(F^ A_ m\in NFQ(n,A)\) for all \(m\in N\); it is called objective if, for all \(n>0\), \(F^ A_ n\not\in NFQ(n- 1,A).\) In the paper the authors give a series of interesting results on the classes NFQ(n,A), some of them are the following: 1) Each truth-table degree contains a 1-subjective set. 2) If A is any set, then A' is 1- subjective. 3) There exist 1-subjective sets A such that for all n and all sets X, \(F^ A_ n\) is not in \(FQ(n-1,X);\) 4) If A is 1-generic, then a is objective; 5) Each non-zero r.e. Turing degree contains an r.e. objective set.

Recommendations

• The complexity of ODD_n^A
• On relativized nondeterministic polynomial-time bounded computations
• On adaptive versus nonadaptive bounded query machines
• Bounded query classes and the difference hierarchy
• Bounded queries to SAT and the Boolean hierarchy

Cites work

• A Theorem on Hypersimple Sets
• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 4024790 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• On the complexity of unique solutions
• Polynomial terse sets
• Semirecursive Sets and Positive Reducibility
• Terse, superterse, and verbose sets
• The complexity of optimization problems

Cited in

(10)

• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• On the computational complexity of querying bounds on differences constraints
• On the structures inside truth-table degrees
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Weakly semirecursive sets
• On Bounded Queries and Approximation
• scientific article; zbMATH DE number 1405575 (Why is no real title available?)
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• The complexity of ODD_n^A
• On adaptive versus nonadaptive bounded query machines

This page was built for publication: Nondeterministic bounded query reducibilities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1120564)