On sets bounded truth-table reducible to P-selective sets

DOI10.1051/ITA/1996300201351MaRDI QIDQ4717049zbMATH OpenOpenAlexFDO

Authors Osamu Watanabe, Thomas Thierauf, Seinosuke Toda

Publication date 13 April 1997

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92529

zbMATH Keywords

NP problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Publication:4942650
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Quasi-linear truth-table reductions to \(p\)-selective sets
• On sets Turing reducible to p-selective sets

Cites work

• A comparison of polynomial time reducibilities
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Approximable sets
• Computing functions with parallel queries to NP
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 512798 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• On reductions of NP sets to sparse sets
• On self-reducibility and weak P-selectivity
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Reductions on NP and p-selective sets
• Relative complexity of checking and evaluating
• Semirecursive Sets and Positive Reducibility
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The complexity of promise problems with applications to public-key cryptography
• The polynomial-time hierarchy
• Turing machines that take advice

Cited in

(12)

• Quasi-linear truth-table reductions to \(p\)-selective sets
• p-selective self-reducible sets: a new characterization of P
• PP is closed under truth-table reductions
• Adaptive versus nonadaptive queries to NP and P-selective sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Schnorr trivial sets and truth-table reducibility
• scientific article; zbMATH DE number 2097995 (Why is no real title available?)
• NONDETERMINISTICALLY SELECTIVE SETS
• scientific article; zbMATH DE number 1414313 (Why is no real title available?)
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Reducibility classes of P-selective sets
• On sets Turing reducible to p-selective sets

This page was built for publication: On sets bounded truth-table reducible to $P$-selective sets

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