Abstract
Black box has been an important tool in studying computational complexity theory and has been used for establishing the hardness of problems. With an exponential growth in big data recently, data-driven computation has utilized black box as a tool for proving solutions to some computational problems. In this note, we present several observations on this new role of black box using reduction techniques in the computational complexity theory.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Du, D.-Z., Ko, K.-I.: Theory of Computational Complexity, 2nd edn. John Wiley and Sons, New York (2014)
Baker, T., Gill, J., Solovay, R.: Relativizations of the P = PNP question. SIAM J. Comput. 4, 431–442 (1975)
Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial time hierarchy. Math. Syst. Theory 17, 13–27 (1984)
Yao, A.: Separating the polynomial time hierarchy by oracle. In: Proceedings of 26th IEEE Symposium on Foundation of Computer Science, pp. 1–10 (1985)
Hastad, J.T.: Almost optimal lower bounds for small depth circuits. In: Proceedings of 18th ACM Symposium on Theory of Computing, pp. 6–20 (1986)
Ko, K.-I.: Relativized polynomial time hierarchies having exactly K levels. In: STOC ’88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 245–253 (1988)
Ko, K.-I.: Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy. J. ACM 37(2), 415–438 (1990)
Ko, K.-I.: A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO Theor. Inf. Appl. 24, 229–240 (1990)
Ko, K.-I.: Separating the low and high hierarchies by oracles. Inf. Comput. 90(2), 156–177 (1991)
Traub, J.F., Werschulz, A.G.: Complexity and Information. Oxford University Press, Oxford (1998)
Acknowledgements
This work is supported in part by NSF under grants 1747818, 1907472, and 1908594.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Jin, R., Wu, W., Thai, M.T., Du, DZ. (2021). Black-Box and Data-Driven Computation. In: Pardalos, P.M., Rasskazova, V., Vrahatis, M.N. (eds) Black Box Optimization, Machine Learning, and No-Free Lunch Theorems. Springer Optimization and Its Applications, vol 170. Springer, Cham. https://doi.org/10.1007/978-3-030-66515-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-66515-9_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66514-2
Online ISBN: 978-3-030-66515-9
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)