Independence results about context-free languages and lower bounds. (English) Zbl 0586.68029
For every axiomatizable, sound formal system F there exist instances about context-free languages, lower bounds of computation and recursive oracles A for which \(NP^ A\neq P^ A\) that are not provable in F for every recursive representation of these problems.
Reviewer: C.Calude
MSC:
| 68Q65 | Abstract data types; algebraic specification |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q45 | Formal languages and automata |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029 |
| [2] | Barker, T.; Gill, J.; Solovay, R., Relativizations of the P = NP? question, SIAM J. Comput., 4, 431-442 (1975) · Zbl 0323.68033 |
| [3] | Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput., 6, 305-327 (1977) · Zbl 0356.68059 |
| [4] | Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [5] | Hajek, P., Arithmetical hierarchy and complexity of computation, Theoret. Comput. Sci., 8, 227-237 (1979) · Zbl 0402.03038 |
| [6] | Harmanis, J., Context-free languages and Turing machine computations, (Proc. Symp. in Applied Math., Vol. 19 (1967), American Mathematical Society: American Mathematical Society Providence, RI), 42-51 · Zbl 0189.29101 |
| [7] | Hartmanis, J., Feasible computations and provable complexity properties, (CBMS-NSF Regional Conference Series in Applied Mathematics, 30 (1978), SIAM) · Zbl 0383.68043 |
| [8] | Hartmanis, J.; Baker, T., Relative succinctness of representation of language and separation of complexity classes, (Proc. 9th Symp. on Mathematics Foundations of Computer Science. Proc. 9th Symp. on Mathematics Foundations of Computer Science, Lecture Notes in Computer Science, 74 (1979), Springer: Springer Berlin), 70-88 · Zbl 0409.68028 |
| [9] | Hartmanis, J.; Hopcroft, J. E., Independence results in computer science, ACM SIGACT News, 8, 4 (1976) |
| [10] | Kowalczyk, W., Some connections between representability of complexity classes and the power of formal systems of reasoning, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 364-369 · Zbl 0563.03024 |
| [11] | Ladner, R. E., On the structure of polynomial time reducibility, J. ACM, 22, 155-171 (1975) · Zbl 0322.68028 |
| [12] | Landweber, L.; Lipton, R.; Robertson, E., On the structure of sets in NP and other complexity classes, Theoret. Comput. Sci., 15, 181-200 (1981) · Zbl 0482.68042 |
| [13] | Mahaney, S., Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, (Proc. 21st IEEE Foundations of Computer Science Symp. (1980)), 42-49 |
| [14] | Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401 |
| [15] | Schöning, U., A uniform approach to obtain diagonal sets in complexity classes, Theoret. Comput. Sci., 18, 95-103 (1982) · Zbl 0485.68039 |
| [16] | Young, P., Some structural properties of polynomial reducibilities and sets in NP, (Proc. 15th ACM Symp. on Theory of Computation (1983)), 392-401 |
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.
