Information Technology Reference
In-Depth Information
[Edm65] J. Edmonds, Paths, trees, and flowers. Canad. J. Math
17
, 449-467 (1965)
[FS08] L. Fortnow, R. Santhanam, Infeasibility of instance compression and succinct PCP's
for NP, in
Proceedings 40th Annual Symposium on Theory of Computing
(ACM, 2008),
pp. 133-142
[GJ79] M.R. Garey, D.S. Johnson,
Computers and Intractability: A Guide to the Theory of
NP-Completeness
(W.H. Freeman, New York, 1979)
[HK71] K. Hoffman, R. Kunze,
Linear Algebra
, 2nd edn. (Prentice Hall, Upper Saddle River,
1971)
[HS65] J. Hartmanis, R.E. Stearns, On the computational complexity of algorithms. Trans.
Am. Math. Soc.
117
, 285-306 (1965)
[HU79] J. Hopcroft, J. Ullman.
Introduction to Automata Theory, Anguages, and Computation
(Addison Wesley, Boston, 1979)
[Imm88] N. Immerman, Nondeterministic space is closed under complementation. SIAM J.
Comput.
17
, 935-939 (1988)
[IPZ01] R. Impagliazzo, R. Paturi, F. Zane, Which problems have strongly exponential com-
plexity? J. Comput. Syst. Sci.
63
(4), 512-530 (2001)
[Kar72] R.M. Karp, Reducibility among combinatorial problems, in
Complexity of Computer
Computations
(1972), pp. 85-103
[KL80] R. Karp, R.J. Lipton, Some connections between nonuniform and uniform complexity
classes, in
Proceedings 12th Annual Symposium on Theory of Computing
(ACM,
1980), pp. 302-309
[Lad75] R.E. Ladner, On the structure of polynomial time reducibility. J. ACM
22
(1), 155-171
(1975)
[Lev73] L.A. Levin, Universal sorting problems. Probl. Peredachi Informatsii
9
(3), 265-266
(1973). in Russian
[Mah82] S.R. Mahaney, Sparse complete sets of NP: Solution of a conjecture of berman and
hartmanis. J. Comput. Syst. Sci.
25
(2), 130-143 (1982)
[MV97] M. Mahajan, V. Vinay, Determinant: Combinatorics, algorithms, and complexity.
Chicago J. Theor. Comput. Sci. 5 (1997)
[Pap94] C.H. Papadimitriou,
Computational Complexity
(Addison-Wesley, Boston, 1994)
[RA00] K. Reinhardt, E. Allender, Making nondeterminism ambiguous. SIAM J. Comput.
29
(4), 1118-1131 (2000)
[Rei08] O. Reingold, Undirected connectivity in log-space. J. ACM
55
(4), 1-24 (2008)
[Sch98] A. Schrijver,
Theory of integer and linear programming
(John Wiley and Sons, Inc.
New York, 1998)
[Sze88] R. Szelepcsényi, The method of forced enumeration for nondeterministic automata.
Acta Informatica
26
, 279-284 (1988)
[Tod91] S. Toda,
Counting problems computationally equivalent to the determinant
. Tech-
nical Report CSIM 91-07, Dept of Computer Sc. and Inf. Math., Univ. of Electro-
Communication, Tokyo, Japan (1991)
[Tut47] W.T. Tutte, The factorization of linear graphs. The J. Lond. Mathe. Soc.
22
, 107-111
(1947)
[Val79] L.G. Valiant, The complexity of computing the permanent. Theor. Comput. Sci.
8
,
189-201 (1979)
[vEB90] P. van Emde Boas, Machine models and simulation, in
Handbook of Theoretical Com-
puter Science, Volume A: Algorithms and Complexity
(Elsevier, Amsterdam, 1990),
pp. 1-66
[Yap83] C.K. Yap, Some consequences of nonuniform conditions on uniform classes. Theor.
Comput. Sci.
26
(3), 287-300 (1983)
