Information Technology Reference
In-Depth Information
Exercise Assuming that the integer determinant is GapL-complete show that
NONSINGULAR
={
M
|
M is a square integer matrix such that
det
(
M
)
1
(
mod 2
) }
is complete for
L under logspace many-one reductions.
The last complexity class we will introduce in this chapter is unambiguous
logspace denoted UL. A logspace bounded nondeterministic Turing machine M
is said to be unambiguous if on every input x
ˇ the machine M has at most one
accepting path. A language L is in the complexity class UL if there is an unambiguous
logspace-bounded nondeterministic Turing machine M that accepts the language L .
A surprising inclusion of complexity classes shown in [ RA00 ] is that NL
poly. 2 Whether NL equals UL or not is an intriguing open problem and is
discussed in Vinodchandran's article in this volume.
UL
/
Acknowledgments I am grateful to Somenath Biswas for his comments and suggestions.
References
[AB09] S. Arora, B. Barak, Computational Complexity, a Modern Approach (Cambridge
University Press, Cambridge, 2009)
[Agr11] M. Agrawal, The Isomorphism Conjecture for NP (World Scientific Press, Singapore,
2011)
[AKL+79] R. Aleliunas, R.M. Karp, R. J. Lipton, L. Lovász, C. Rackoff, Random walks, uni-
versal traversal sequences, and the complexity of maze problems, in FOCS (1979),
pp. 218-223. IEEE
[AO96] E. Allender, M. Ogihara, Relationships among PL, # and the determinant. RAIRO
Theor. Inf. Appl. 30 (1), 1-21 (1996)
[BDG88] J.L. Balcázar, J. Diaz, J. Gabarro, Structural Complexity I and II (Springer, Heidelberg,
1988)
[BDHM92] G. Buntrock, C. Damm, U. Hertrampf, C. Meinel, Structure and importance of
logspace-MOD class. Theory Comput. Syst. 25 (3), 223-237 (1992)
[BH77] L. Berman, J. Hartmanis, On isomorphisms and density of np and other complete sets.
SIAM J. Comput. 6 (2), 305-322 (1977)
[BH08] H. Buhrman, J. Hitchcock, Np-hard sets are exponentially dense unless conp p/poly,
in IEEE Conference on Computational Complexity (2008), pp. 1-7
[CH53] R. Courant, D. Hilbert, Methods in Mathematical Physics , vol. I (Interscience
Publishers, Hoboken, 1953)
[Cob64] A. Cobham, The intrinsic computational difficulty of functions, in International
Congress for Logic, Methodology and Philosophy of Science (ICLMPS) (1964)
[Coo71] S.A. Cook, The complexity of theorem proving procedures,
in stoc71 (1971),
pp. 151-158
[DF03] R.G. Downey, L. Fortnow, Uniformly hard languages. Theor. Comput. Sci. 2 (298),
303-315 (2003)
2 This inclusion is surprising because the definition of UL
poly is quite stringent: the nondetermin-
istic logspace machine is required to be unambiguous for every advice string.
/
Search WWH ::




Custom Search