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.
/