NDLI: On the power of unambiguity in log-space

Please wait, while we are loading the content...

On the power of unambiguity in log-space

Content Provider	Springer Nature Link
Author	Vidchandran, N. V. Tewari, Raghunath Pavan, A.
Copyright Year	2012
Abstract	We report progress on the NL versus UL problem. We show that counting the number of s-t paths in graphs where the number of s-v paths for any v is bounded by a polynomial can be done in FUL: the unambiguous log-space function class. Several new upper bounds follow from this including $${{{ReachFewL} \subseteq {UL}}}$$ and $${{{LFew} \subseteq {UL}^{FewL}}}$$ We investigate the complexity of min-uniqueness—a central notion in studying the NL versus UL problem. In this regard we revisit the class OptL[log n] and introduce UOptL[log n], an unambiguous version of OptL[log n]. We investigate the relation between UOptL[log n] and other existing complexity classes. We consider the unambiguous hierarchies over UL and UOptL[log n]. We show that the hierarchy over UOptL[log n] collapses. This implies that $${{{ULH} \subseteq {L}^{{promiseUL}}}}$$ thus collapsing the UL hierarchy. We show that the reachability problem over graphs embedded on 3 pages is complete for NL. This contrasts with the reachability problem over graphs embedded on 2 pages, which is log-space equivalent to the reachability problem in planar graphs and hence is in UL.
Ending Page	670
Page Count	28
Starting Page	643
File Format	PDF
ISSN	10163328
e-ISSN	14208954
Journal	Computational complexity
Issue Number	4
Volume Number	21
Language	English
Publisher	SP Birkhäuser Verlag Basel
Publisher Date	2012-09-25
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	log-space optimization Log-space complexity hardness Complexity classes (hierarchies, relations among complexity classes, etc.) Computational Mathematics and Numerical Analysis unambiguous computations graph reachability Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Algorithm Analysis and Problem Complexity Models of computation (Turing machines, etc.)
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

ReachFewL = ReachUL

Division in logspace-uniform NC1

Quantum and Probabilistic Computers Rigorously Powerful than Traditional Computers, and Derandomization

Hardness as randomness: a survey of universal derandomization

Complexity of Hard-Core Set Proofs

On the connection between interval size functions and path counting

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines

A theory of NP-completeness and ill-conditioning for approximate real computations

How NP got a new definition: a survey of probabilistically checkable proofs

On the power of unambiguity in log-space

Similar Documents

ReachFewL = ReachUL

Division in logspace-uniform NC1

Quantum and Probabilistic Computers Rigorously Powerful than Traditional Computers, and Derandomization

Hardness as randomness: a survey of universal derandomization

Complexity of Hard-Core Set Proofs

On the connection between interval size functions and path counting

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines

A theory of NP-completeness and ill-conditioning for approximate real computations

How NP got a new definition: a survey of probabilistically checkable proofs

On the power of unambiguity in log-space