ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES

DOI10.1142/S0129054105003376zbMath1080.68039MaRDI QIDQ5704373

Hemaspaandra, Lane A., Piotr Faliszewski

Publication date: 14 November 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

P-selectivityAdvice complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• An observation on associative one-way functions in complexity theory
• Optimal advice
• On self-reducibility and weak P-selectivity
• Qualitative relativizations of complexity classes
• The maximum value problem and NP real numbers
• Some observations on NP real numbers and P-selective sets
• Reductions on NP and p-selective sets
• Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
• \(p\)-Selective sets and reducing search to decision vs. self-reducibility
• PP is as Hard as the Polynomial-Time Hierarchy
• Quantitative Relativizations of Complexity Classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Algebraic Properties for Selector Functions
• NONDETERMINISTICALLY SELECTIVE SETS
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy