Information Technology Reference
In-Depth Information
[AB96] M. Agrawal, S. Biswas, Polynomial-time isomorphism of 1-L-complete sets. J. Com-
put. Syst. Sci.
53
(2), 155-160 (1996)
[AW09] M. Agrawal, O. Watanabe. One-way functions and the Berman-Hartmanis conjecture.
in
Proceedings IEEE Conference on Computational Complexity
(2009). pp. 194-202
[All88] E. Allender, Isomorphisms and 1-L reductions. J. Comput. Syst. Sci.
36
(3), 336-350
(1988)
[All01] E. Allender, in
Some Pointed Questions Concerning Asymptotic Lower Bounds, and
News From the Isomorphism Front
, ed. byG. Paun, G. Rozenberg, A. Salomaa. Current
Trends in Theoretical Computer Science: Entering the 21st Century (World Scientific
Press, 2001), pp. 25-41
[ABI97] E. Allender, J.L. Balcázar, N. Immerman, A first-order isomorphism theorem. SIAM
J. Comput.
26
(2), 557-567 (1997)
[AG91] E. Allender, V. Gore, Rudimentary reductions revisited. Inf. Process. Lett.
40
(2), 89-95
(1991)
[BH77] L. Berman, J. Hartmanis, On isomorphism and density of NP and other complete sets.
SIAM J. Comput.
6
, 305-322 (1977)
[BH92] H.-J. Burtschick, A. Hoene, in
The Degree Structure of 1-L Reductions
, ed. by I.M.
Havel, V. Koubek. MFCS, Lecture Notes in Computer Science vol. 629 (Springer,
1992), pp. 153-161
[CSB07] V. Choudhary, A.K. Sinha, S. Biswas. Universality for nondeterministic logspace. in
Proceedings 1st International Conference on Language and Automata Theory and
Applications (LATA)
( 2007), pp. 103-114
[CM87] S.A. Cook, P. McKenzie, Problems complete for deterministic logarithmic space. J.
Algorithms
8
(3), 385-394 (1987)
[FSS84] M.L. Furst, J.B. Saxe, M. Sipser, Parity, circuits, and the polynomial-time hierarchy.
Math. Syst. Theor.
17
(1), 13-27 (1984)
[GJ79] M.R. Garey, D.S. Johnson,
Computers and Intractability: A Guide to the theory of
NP-completeness
(W.H. Freeman and Company, New York, 1979)
[HHP07] R.C. Harkins, J.M. Hitchcock, A. Pavan, Strong reductions and isomorphism of com-
plete sets. in
Proceedings Conference on Foundations of Software Technology and
Theoretical Computer Science (FST&TCS)
. Lecture Notes in Computer Science vol.
4855 (Springer, 2007), pp. 168-178
[HIM78] J. Hartmanis, N. Immerman, S.R. Mahaney, One-way log-tape reductions. in
Pro-
ceedings IEEE Symposium on Foundation of Computer Science (FOCS)
(1978). pp.
65-72
[HM81] J. Hartmanis, S.R. Mahaney, Languages simultaneously complete for one-way and
two-way log-tape automata. SIAM J. Comput.
10
(2), 383-390 (1981)
[HH93] L.A. Hemachandra, A. Hoene, Collapsing degrees via strong computation. J. Comput.
Syst. Sci.
46
(3), 363-380 (1993)
[IW97] R. Impagliazzo, A. Wigderson,
P
BPP
if
E
requires exponential circuits: deran-
domizing the XOR lemma. in
Proceedings ACM Symposium on Theory of Computing
(STOC)
(1997), pp. 220-229
[Jon75] N.D. Jones, Space-bounded reducibility among combinatorial problems. J. Comput.
Syst. Sci.
11
(1), 68-85 (1975)
[JY85] D. Joseph, P. Young, Some remarks on witness functions for nonpolynomial and non-
complete sets in NP. Theor. Comput. Sci.
39
, 225-237 (1985)
[KC00] V. Kabanets, J.-Y. Cai, Circuit minimization problem. in
Proceedings ACM Symposium
on Theory of Computing 456 (STOC)
(2000), pp. 73-79
[Pos44] E.L. Post, Recursively enumerable sets of positive integers and their decision problems.
Bull. Am. Math. Soc.
50
, 284-316 (1944)
[Rog67] H. Rogers,
Theory of Recursive Functions and Effective Computability
. (McGraw-Hill,
New York, 1967)
[Soa87] R.I. Soare,
Recursively-Enumerable Sets and Degrees
(Springer, Berlin, 1987)
[Wan91] J. Wang, On p-creative sets and p-completely creative sets. Theor. Comput. Sci.
85
(1),
1-31 (1991)
=
