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

Flajolet, P. ; Steyaert, J. M.

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

MR Zbl

@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},
     series = {Ast\'erisque},
     pages = {53--72},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {38-39},
     year = {1976},
     mrnumber = {457164},
     zbl = {0361.68067},
     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
SP  - 53
EP  - 72
IS  - 38-39
PB  - Société mathématique de France
UR  - http://www.numdam.org/item/AST_1976__38-39__53_0/
LA  - fr
ID  - AST_1976__38-39__53_0
ER  -

%0 Book Section
%A Flajolet, P.
%A Steyaert, J. M.
%T Hiérarchies de complexité et réductions entre problèmes
%B Journées algorithmiques
%A Collectif
%S Astérisque
%D 1976
%P 53-72
%N 38-39
%I Société mathématique de France
%U http://www.numdam.org/item/AST_1976__38-39__53_0/
%G fr
%F AST_1976__38-39__53_0

Flajolet, P.; Steyaert, J. M. Hiérarchies de complexité et réductions entre problèmes, dans Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 53-72. http://www.numdam.org/item/AST_1976__38-39__53_0/

Bibliographie
Cité par

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

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

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

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

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

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

[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 | Zbl

[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 | Zbl

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

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

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

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

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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