On helping by robust oracle machines. (English) Zbl 0635.68039
The concept of helping using robust oracle Turing machines (TM) was first introduced by U. Schöning [Theor. Comput. Sci. 40, 57–66 (1985; Zbl 0574.68041)]. An oracle TM is robust if its output on an input \(x\) does not change when oracle changes its answers to the queries made by the TM. Thus, an oracle can only affect the computation time used by the machine. An oracle is said to help a robust TM if the machine runs in polynomial time using this oracle. Certain interesting structural properties about helping sets in NP have been observed by Schöning.
Some more are observed in this paper. For example, the class \(\mathrm{UP}\cap \mathrm{co-UP}\) helps exactly sets in the same class, where UP is the class of sets computable by unambiguous NP machines [L. G. Valiant, Inf. Process. Lett. 5, 20–23 (1976; Zbl 0342.68028)]. New notions of helping such as one-sided helping, self-helping are studied and compared with other standard notions of complexity theory such as self-reducibility and sparseness. Several known properties of these standard complexity notions are reproved from the viewpoint of helping.
Some more are observed in this paper. For example, the class \(\mathrm{UP}\cap \mathrm{co-UP}\) helps exactly sets in the same class, where UP is the class of sets computable by unambiguous NP machines [L. G. Valiant, Inf. Process. Lett. 5, 20–23 (1976; Zbl 0342.68028)]. New notions of helping such as one-sided helping, self-helping are studied and compared with other standard notions of complexity theory such as self-reducibility and sparseness. Several known properties of these standard complexity notions are reproved from the viewpoint of helping.
Reviewer: Ker-I Ko
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
Keywords:
helping; robust oracle Turing machines; NP; complexity theory; self-reducibility; sparsenessReferences:
| [1] | Adleman, L., Two theorems on random polynomial time, Proc. 19th IEEE Symp. on Foundations of Computer Science, 75-83 (1978) |
| [2] | Berman, L.; Hartmanis, J., On isomorphism and density of NP and other complete sets, SIAM J. Comput., 6, 305-327 (1977) · Zbl 0356.68059 |
| [3] | Cook, S. A., The complexity of theorem-proving procedures, Proc. 3rd ACM Symp. on Theory of Computing, 151-158 (1971) · Zbl 0253.68020 |
| [4] | Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 675-695 (1977) · Zbl 0366.02024 |
| [5] | Karp, R. M.; Lipton, R. J., Some connections between nonuniform and uniform complexity classes, Proc. 12th ACM Symp. on Theory of Computing, 302-309 (1980) |
| [6] | Ko, K., On self-reducibility and weak \(p\)-selectivity, J. Comput. System Sci., 26, 209-221 (1983) · Zbl 0519.68062 |
| [7] | Ko, K.; Schöning, U., On circuit-size complexity and the low hierarchy in NP, SIAM J. Comput., 14, 41-51 (1985) · Zbl 0562.68033 |
| [8] | Mahaney, S., Sparse complete sets for NP: solution to a conjecture by Berman and Hartmanis, J. Comput. System Sci., 25, 130-143 (1982) · Zbl 0493.68043 |
| [9] | Meyer, A.; Paterson, M., With what frequency are apparently intractable problems difficult? (1979), Lab. for Computer Science, MIT: Lab. for Computer Science, MIT Cambridge, MA, Tech. Rept., MIT/LCS/TM-126 |
| [10] | Schöning, U., A low and a high hierarchy within NP, J. Comput. System Sci., 27, 14-28 (1983) · Zbl 0515.68046 |
| [11] | Schöning, U., Robust algorithms: a different approach to oracles, Theoret. Comput. Sci., 40, 57-66 (1985) · Zbl 0574.68041 |
| [12] | Schöning, U., Complexity and Structure, (Lecture Notes in Computer Science, 211 (1986), Springer: Springer Berlin) · Zbl 0872.68048 |
| [13] | Selman, A. L., Analogues of semirecursive sets and effective reducibilities to the study of NP complexity, Inform. and Control, 52, 36-51 (1982) · Zbl 0504.03022 |
| [14] | Selman, A. L., Remarks about natural self-reducible sets in NP and public-key cryptosystems (1984), Iowa State University, Manuscript |
| [15] | Valiant, L. G., Relative complexity of checking and evaluating, Inform. Process. Lett., 5, 20-23 (1976) · Zbl 0342.68028 |
| [16] | Wrathall, C., Complete sets and the polynomial-time hierarchy, Theorem. Comput. Sci., 3, 23-33 (1977) · Zbl 0366.02031 |
| [17] | Zachos, S., Probabilistic quantifiers, adversaries, and complexity classes: an overview, (Proc. Conf. on Structure in Complexity Theory. Proc. Conf. on Structure in Complexity Theory, Lecture Notes in Computer Science, 223 (1986), Springer: Springer Berlin), 383-400 · Zbl 0632.03035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
