Hiérarchies de complexité et réductions entre problèmes

Journées algorithmiques, Astérisque no. 38-39 (1976), p. 53-72

@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},
     pages = {53-72},
     zbl = {0361.68067},
     mrnumber = {457164},
     language = {fr},
     url = {http://www.numdam.org/item/AST_1976__38-39__53_0}
}

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/

References

[1] Aho, Hopcroft, Ullman (1974) : The design and Analysis of Computer Algorithms, Addison Wesley. | MR 413592 | Zbl 0326.68005

[2] Borodin (1973) : Computational Complexity, Theory and Practice ; in Currents in the Theory of Computing, Prentice Hall. | MR 426495

[3] Cook (1971) : The Complexity of theorem proving Procedures, 3rd ACM SIGACT. | Article | Zbl 0253.68020

[4] Cook (1971) : Linear time simulation of deterministic two-way pushdown automata, IFIP-Ljubljana. | Zbl 0255.68015

[5] Cook (1973) : An observation on Time-Storage Trade-off, 5th ACMSIGACT. | Article | MR 411238 | Zbl 0305.68066

[6] Cook, Reckhow (1973) : Time bounded Random Access Machines, JCSS 7. | Article | MR 327074 | Zbl 0284.68038

[7] Even, Tarjan (1975) : A combinatorial problem which is Polynomial Space Complete, in 7th ACM SIGACT.

[8] Fischer, Rabin (1974) : Super-exponential Complexity of Presburger Arithmetic, MIT C.C. Rep. | MR 366646 | Zbl 0319.68024

[9] Flajolet, Steyaert (1975) : Complexité logique des Algorithmes. Notes de l'Ecole IRIA de Complexité, Berder 1974.

[10] Garey, Johnson, Stockmeyer (1974) : Some simplified NP-complete problems, 6th ACM. SIGACT. | MR 418510 | Zbl 0338.05120

[11] Hennie, Stearns (1966) : Two tape simulation of multitape Turing machines, JACM 13. | Article | MR 210521 | Zbl 0148.24801

[12] Karp (1972) : Reducibility among Combinatorial Problems, in Complexity of Computer Computations, Plenum Press. | Article | MR 378476 | Zbl 0366.68041

[13] Karp (1975) : On the Computational Complexity of Combinatorial problems, Network 5. | Zbl 0324.05003

[14] Kleene (1952) : Introduction to metamathematics, North Holland. | MR 51790 | Zbl 0047.00703

[15] Knuth (1968-73) : The Art of Computer Programming I, II, III, Addison Wesley. | MR 286317 | Zbl 0191.17903

[16] Meyer, Stockmeyer (1973) : The equivalence problem for regular expression with squaring requires exponential space, in 13th IEEE SWAT.

[18] Minsky (1967) : Computation : Finite and Infinite Machines, Prentice Hall. | MR 356580 | Zbl 0195.02402

[19] Pratt, Rabin, Stockmeyer (1974) : A Characterisation of the Power of Vector Machines. | MR 451870 | Zbl 0381.68039

[20] Rabin (1974) : Theoretical Impediments to Artificial Intelligence, in IFIP Stockholm. | MR 421186 | Zbl 0296.68054

[21] Rackoff (1975) : The Computational Complexity of some logical theories, These MIR.

[22] Sahni (1972) : Some related problems from network flows, game theory and integer programming, in 13th IEEE SWAT.

[23] Savitch (1970) : Relationships between non-deterministic and deterministic tape complexities, JCSS 4. | MR 266702 | Zbl 0188.33502

[24] Simon (1974) : On the power of multiplication in Random Access Machines, Cornell Uni. CS Rep.

[25] Yasuhara (1971) : Recursive Function theory and logic, Academic Press. | MR 313027 | Zbl 0254.02002

[26] Hopcroft, Paul, Valiant (1975) : On time versus space and related problems, 16th F.O.C.S. | MR 428789