On the Autoreducibility of Functions
Tóm tắt
This paper studies the notions of self-reducibility and autoreducibility. Our main result regarding length-decreasing self-reducibility is that any complexity class
$\mathcal{C}$
that has a (logspace) complete language and is closed under polynomial-time (logspace) padding has the property that if all
$\mathcal{C}$
-complete languages are length-decreasing (logspace) self-reducible then
$\mathcal{C}\subseteq \mathrm {P}$
(
$\mathcal {C}\subseteq \mathrm {L}$
). In particular, this result applies to NL, NP and PSPACE. We also prove an equivalent of this theorem for function classes (for example, for #P). We also show that for several hard function classes, in particular for #P, it is the case that all their complete functions are deterministically autoreducible. In particular, we show the following result. Let f be a #P parsimonious function with two preimages of 0. We show that there are two FP functions h and t such that for all inputs x we have f(x)=t(x)+f(h(x)), h(x)≠x, and t(x)∈{0,1}. Our results regarding single-query autoreducibility of #P functions can be contrasted with random self-reducibility for which it is known that if a #P complete function were random self-reducible with one query then the polynomial hierarchy would collapse.
Tài liệu tham khảo
Abadi, M., Feigenbaum, J., Kilian, J.: On hiding information from an oracle. J. Comput. Syst. Sci. 39(1), 21–50 (1989)
Ambos-Spies, K.: P-mitotic sets. In: Logic and Machines, pp. 1–23. Springer, Berlin (1983)
Balcázar, J.: Self-reducibility. J. Comput. Syst. Sci. 41(3), 367–388 (1990)
Beigel, R., Feigenbaum, J.: On being incoherent without being very hard. Comput. Complex. 2(1), 1–17 (1992)
Bovet, D., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice-Hall, New York (1993)
Buhrman, H., Torenvliet, L.: P-selective self-reducible sets: A new characterization of P. J. Comput. Syst. Sci. 53(2), 210–217 (1996)
Buhrman, H., Fortnow, L., van Melkebeek, D., Torenvliet, L.: Separating complexity classes using autoreducibility. SIAM J. Comput. 29(4), 1497–1520 (2000)
Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM J. Comput. 22(5), 994–1005 (1993)
Feigenbaum, J., Kannan, S., Nisan, N.: Lower bounds on random-self-reducibility. In: Proceedings of the 5th Structure in Complexity Theory Conference, pp. 100–109. IEEE Computer Society, Los Alamitos (1990)
Feigenbaum, J., Fortnow, L., Lund, C., Spielman, D.: The power of adaptiveness and additional queries in random-self-reductions. In: Proceedings of the 7th Structure in Complexity Theory Conference, pp. 338–346. IEEE Computer Society, Los Alamitos (1992). Final version appears in Computational Complexity, vol. 4, pp. 158–174 (1994)
Fenner, S., Fortnow, L., Kurtz, S.: Gap-definable counting classes. J. Comput. Syst. Sci. 48(1), 116–148 (1994)
Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6(4), 675–695 (1977)
Glaßer, C., Ogihara, M., Pavan, A., Selman, A., Zhang, L.: Autoreducibility, mitocity, and immunity. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 3153, pp. 387–398. Springer, Berlin (2005)
Gupta, S.: On the closure of certain function classes under integer division by polynomially bounded functions. Inf. Process. Lett. 44(2), 205–210 (1992)
Gupta, S.: Closure properties and witness reduction. J. Comput. Syst. Sci. 50(3), 412–432 (1995)
Hemaspaandra, L., Ogihara, M.: The Complexity Theory Companion. Springer, New York (2002)
Joseph, D., Young, P.: Some remarks on witness functions for non-polynomial and non-complete sets in NP. Theor. Comput. Sci. 39(2–3), 225–237 (1985)
Köbler, J., Schöning, U., Torán, J.: On counting and approximation. Acta Inform. 26(4), 363–379 (1989)
Krentel, M.: The complexity of optimization problems. J. Comput. Syst. Sci. 36(3), 490–509 (1988)
Ladner, R.: Mitotic recursively enumerable sets. J. Symb. Log. 38(2), 199–211 (1973)
Ladner, R., Lynch, N.: Relativization of questions about log space computability. Math. Syst. Theory 10(1), 19–32 (1976)
Ladner, R., Lynch, N., Selman, A.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1(2), 103–124 (1975)
Lipton, R.: New directions in testing. In: Feigenbaum, J., Merritt, M. (eds.) Distributed Computing and Cryptography. DIMACS series in Discrete Mathematics and Theoretical Computer Science, pp. 191–202. American Mathematical Society, Providence (1991)
Meyer, A., Paterson, M.: With what frequency are apparently intractable problems difficult? Technical Report MIT/LCS/TM-126, Laboratory for Computer Science, MIT, Cambridge, MA (1979)
Ogiwara, M., Hemachandra, L.: A complexity theory for feasible closure properties. J. Comput. Syst. Sci. 46(3), 295–325 (1993)
Pagourtzis, A., Zachos, S.: The complexity of counting functions with easy decision version. In: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 4162, pp. 741–752. Springer, Berlin (2006)
Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)
Schnorr, C.: Optimal algorithms for self-reducible problems. In: Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming, pp. 322–337. Edinburgh University Press, Edinburgh (1976)
Simon, J.: On some central problems in computational complexity. Ph.D. thesis, Cornell University, Ithaca, NY, January (1975). Available as Cornell Department of Computer Science Technical Report TR75-224
Torán, J.: Complexity classes defined by counting quantifiers. J. ACM 38(3), 753–774 (1991)
Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979)
Vollmer, H.: On different reducibility notions for function classes. In: Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 775, pp. 449–460. Springer, Berlin (1994)
Wagner, K.: The complexity of combinatorial problems with succinct input representations. Acta Inform. 23(3), 325–356 (1986)
Watanabe, O., Toda, S.: Polynomial time 1-Turing reductions from #PH to #P. Theor. Comput. Sci. 100(1), 205–221 (1992)
Yao, A.: Coherent functions and program checkers. In: Proceedings of the 22nd ACM Symposium on Theory of Computing, pp. 84–94. Assoc. Comput. Mach., New York (1990)
Zankó, V.: #P-completeness via many-one reductions. Int. J. Found. Comput. Sci. 2(1), 76–82 (1991)