@incollection{AST_1976__38-39__53_0, author = {Flajolet, P. and Steyaert, J. M.}, title = {Hi\'erarchies de complexit\'e et r\'eductions entre probl\`emes}, booktitle = {Journ\'ees algorithmiques}, author = {Collectif}, series = {Ast\'erisque}, publisher = {Soci\'et\'e math\'ematique de France}, number = {38-39}, year = {1976}, zbl = {0361.68067}, mrnumber = {457164}, language = {fr}, url = {http://www.numdam.org/item/AST_1976__38-39__53_0/} }
TY - CHAP AU - Flajolet, P. AU - Steyaert, J. M. TI - Hiérarchies de complexité et réductions entre problèmes BT - Journées algorithmiques AU - Collectif T3 - Astérisque PY - 1976 DA - 1976/// IS - 38-39 PB - Société mathématique de France UR - http://www.numdam.org/item/AST_1976__38-39__53_0/ UR - https://zbmath.org/?q=an%3A0361.68067 UR - https://www.ams.org/mathscinet-getitem?mr=457164 LA - fr ID - AST_1976__38-39__53_0 ER -
Flajolet, P.; Steyaert, J. M. Hiérarchies de complexité et réductions entre problèmes, in Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 53-72. http://www.numdam.org/item/AST_1976__38-39__53_0/
[1] The design and Analysis of Computer Algorithms, Addison Wesley. | MR | Zbl
, , (1974) :[2] Computational Complexity, Theory and Practice ; in Currents in the Theory of Computing, Prentice Hall. | MR
(1973) :[3] The Complexity of theorem proving Procedures, 3rd ACM SIGACT. | DOI | Zbl
(1971) :[4] Linear time simulation of deterministic two-way pushdown automata, IFIP-Ljubljana. | Zbl
(1971) :[5] An observation on Time-Storage Trade-off, 5th ACMSIGACT. | DOI | MR | Zbl
(1973) :[6] Time bounded Random Access Machines, JCSS 7. | DOI | MR | Zbl
, (1973) :[7] A combinatorial problem which is Polynomial Space Complete, in 7th ACM SIGACT.
, (1975) :[8] Super-exponential Complexity of Presburger Arithmetic, MIT C.C. Rep. | MR | Zbl
, (1974) :[9] Complexité logique des Algorithmes. Notes de l'Ecole IRIA de Complexité, Berder 1974.
, (1975) :[10] Some simplified NP-complete problems, 6th ACM. SIGACT. | MR | Zbl
, , (1974) :[11] Two tape simulation of multitape Turing machines, JACM 13. | DOI | MR | Zbl
, (1966) :[12] Reducibility among Combinatorial Problems, in Complexity of Computer Computations, Plenum Press. | DOI | MR | Zbl
(1972) :[13] On the Computational Complexity of Combinatorial problems, Network 5. | Zbl
(1975) :[14] Introduction to metamathematics, North Holland. | MR | Zbl
(1952) :[15] The Art of Computer Programming I, II, III, Addison Wesley. | MR | Zbl
(1968-73) :[16] The equivalence problem for regular expression with squaring requires exponential space, in 13th IEEE SWAT.
, (1973) :[18] Computation : Finite and Infinite Machines, Prentice Hall. | MR | Zbl
(1967) :[19] A Characterisation of the Power of Vector Machines. | MR | Zbl
, , (1974) :[20] Theoretical Impediments to Artificial Intelligence, in IFIP Stockholm. | MR | Zbl
(1974) :[21] The Computational Complexity of some logical theories, These MIR.
(1975) :[22] Some related problems from network flows, game theory and integer programming, in 13th IEEE SWAT.
(1972) :[23] Relationships between non-deterministic and deterministic tape complexities, JCSS 4. | MR | Zbl
(1970) :[24] On the power of multiplication in Random Access Machines, Cornell Uni. CS Rep.
(1974) :[25] Recursive Function theory and logic, Academic Press. | MR | Zbl
(1971) :[26] On time versus space and related problems, 16th F.O.C.S. | MR
, , (1975) :