×

zbMATH — the first resource for mathematics

On self-reducibility and weak P-selectivity. (English) Zbl 0519.68062

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adleman, L., Two theorems on random polynomial time, (), 75-83
[2] Bennett, C.H.; Gill, J., Relative to a random oracle A, PA ≠ NPA ≠ co-NPA with probability 1, SIAM J. comput., 10, 96-113, (1981)
[3] Bennison, V.L., Some lowness properties and computational complexity sequences, Theoret. comput. cci., 6, 233-254, (1978) · Zbl 0401.68021
[4] Bennison, V.L., Information content characterizations of complexity theoretic properties, (), 58-66
[5] Berman, L., On the structure of complete sets: almost everywhere complexity and infinitely often speed up, (), 76-80
[6] Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (), 63-71
[7] Berman, L.; Hartmanis, J., On isomorphism and densities of NP and other complete sets, SIAM J. comput., 6, 305-322, (1977) · Zbl 0356.68059
[8] Cook, S.A., The complexity of theorem-proving procedures, (), 151-158 · Zbl 0363.68125
[9] Fortune, S., A note on sparse complete sets, SIAM J. comput., 8, 431-433, (1979) · Zbl 0415.68006
[10] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (), 302-309
[11] Ko, K., The maximum value problem and NP real numbers, J. comput. system sci., 24, 15-35, (1982) · Zbl 0481.03038
[12] {\scK. Ko}, A note on circuit-size complexity and the low hierarchy in NP, SIAM J. Comput., to appear. · Zbl 0562.68033
[13] Ko, K.; Moore, D.J., Completeness, approximation and density, SIAM J. comput., 10, 787-796, (1981) · Zbl 0468.68051
[14] Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. comput. sci., 1, 103-213, (1975) · Zbl 0321.68039
[15] Mahaney, S.R., Sparse complete sets for NP: solution of a conjecture by berman and hartmanis, (), 54-60
[16] Meyer, A.; Paterson, M., With what frequency are apparently intractable problem difficult?, MIT tech. rep., MIT/LES/TM-126, (1979)
[17] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[18] {\scU. Schöning}, A low and a high hierarchy within NP, J. Comput. System Sci., to appear.
[19] Selman, A.L., P-selective sets, tally languages and the behavior of polynomial time reducibilities on NP, Math. systems teory, 13, 55-65, (1979) · Zbl 0405.03018
[20] Selman, A.L., Some observations on NP real numbers and p-selective sets, J. comput. system sci., 23, 326-332, (1981) · Zbl 0486.03020
[21] Selman, A.L., Reductions on NP and p-selective sets, Theoret. comput. sci., 19, 287-304, (1982) · Zbl 0489.03016
[22] Scare, R.I., Computational complexity, speedable and levelable sets, J. symbolic logic, 42, 545-563, (1977) · Zbl 0401.68020
[23] Stockmeyer, L.J.; Meyer, A.R., Word problems requiring exponential time, (), 1-9 · Zbl 0359.68050
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.