Pierwszy problem milenijny: czy NP = P?

• Autorzy: Pacholski Leszek

Identyfikatory

DOI

10.14708/wm.v40i01.4968

• Języki publikacji: PL
• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Wiadomości Matematyczne
• Rocznik: 2004
• Tom: T. 40, Nr 1
• Strony: 1--21
• Opis fizyczny: Bibliogr. 33 poz.

Twórcy

autor

Pacholski Leszek

• University of Wrocław: Wrocław, Poland, PL

• https://orcid.org/0000-0001-9651-6279

Bibliografia

• [1] M. Ajtai, Σ_1^l-formulae on finite structures, Annals of Pure and Applied Logic 24 (1983), 1-48.
• [2] M. Ajtai, The complezity of the pigeonhole principle, Proc. 29th IEEE FOCS (1988), 346-355.
• [3] T. Baker, J. Gili, and R. Solovay, Relativisation of the P=?NP question, SIAM Journal on Computing 4 (1975), 431-442.
• [4] C. Bennet and J. Gill, Relative to a random oracie A, P^A ≠ NP^A ≠ co-NP^A, with probability 1, SIAM Journal on Computing 10 (1981), 96-113.
• [5] L. Berman and J. Hartmanis, On isomorphism and density pf NP and other complete sets, SIAM Journal on Computing 6 (1977), 305-322.
• [6] A. A. Bulatov, A dichotomy theorem for constraints on a three-element sets, Proceedings of the 43rd Symposium on Foundations of Computer Science (2002), 649-658.
• [7] R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hast ad and D. Ranjan, The random oracie hypothesis is false Journal of Computer and System Sciences 49 (1994), 24-39.
• [8] S. A. Cook, The complexity of theorem proving procedures, Proc. 3rd ACM STOC (1971), 151-158
• [9] S. A. Cook and R. Reckhow, The relative efficiency of propositional proof Systems, Journal of Symbolic Logic 44 (1979), 36-50.
• [10] M. Davis and H. Putnam, A computing procedure for quantification theory, Journal of ACM 7 (1960), 201-215.
• [11] R. Fagin, Generalized first-order spectra and polynomial time recognizable sets, Complexity of Computations, SAIM-AMS Proceedings 7 (1974), 43-73.
• [12] M. Furst and J. B. Saxe and M. Sipser, Parity, circuits and the polynomial time hierarchy, Mathematical System Theory 17 (1984), 13-27.
• [13] A. Haken, The intractability of resolution, Theoretical Computer Science 39 (1985), 297-308.
• [14] N. Immerman, Relational queries computable in polynomial time, Proc. 14th ACM STOC (1982), 147-152. Pełna wersja Information and Control (1986), 86-104.
• [15] N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17 (1988), 935-938.
• [16] N. Immerman, Descriptiue Complexity, Springer Verlag (1999).
• [17] N. D. Jones and A. L. Selman, Turing machines and the spectra of first-order formulas, Journal of Symbolic Logic 39 (1974), 139-150.
• [18] R. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (1972), 85-103.
• [19] R. Karp and R. Lipton, Turing machines that take advice, L’Ensegnement Mathématique 28 (1982), 191-209.
• [20] J. Krajicek, P. Pudla k, and A. Woods, Exponential lower bounds to the size of bounded depth Freqe proofs of the pigeonhole principle, Random Structures and Algorithms 7 (1995), 15-39.
• [21] R. E. Ladner, On the structure of polynomial time reducibility, Journal of ACM 22 (1975), 155-171.
• [22] C. Lund, L. Fortno w, H. Karloff, and N. Nisan, Algebraic methods for interactiue proof systems, Journal of ACM 39 (1992), 859-868.
• [23] S. Mahaney, Sparse complete sets for NP Solution of a conjecture of Berma and Hartmanis, Journal of Computer and System Science 25 (1982), 130-143.
• [24] T. Pitassi, P. Beame, and R. Impagliazzo, Exponential lower bounds for the pigeonhole principle, Computationa Complexity 3 (1993), 97-140.
• [25] A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Doklady Akademi Nauk SSSR 281 (1985), 798-801.
• [26] J. A. Robinson, A machine oriented logic based on resolution principle, Journal of ACM 12 (1983), 23-41.
• [27] W. Savitch, Relationship between nondeterministic and deterministic tape classes, Journal of Computer and System Science 4 (1970), 177-192.
• [28] T. J. Schaefer, The complexity of satisfiability problem, Proc. lOth ACM Symposium on Theory of Computing (1978), 216-226.
• [29] A. Shamir, IP=PSPACE, Journal of ACM 39 (1992), 869-877.
• [30] C. E. Shannon, The synthesis of two-terminal switching circuits, Bell Systems Technical Journal 28 (1949), 59-98.
• [31] R. Smolensky, Algebraic methods in the theoryof lower bounds for Boolean circuit complexity, Proc. 19th Annual ACM Symposium on Theory of Computing (1987), 77- 82.
• [32] R. Szelepcsnényi, The method of forced enumeration for nondeterministic automata, Acta Informatica 26 (1988), 279-284.
• [33] M. Vardi, Complexity of relational query languages, Proc. 14th ACM STOC (1982), 137-146.