Access Restriction

Author Chen, Yijia ♦ Flum, Jrg
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Optimal algorithms ♦ Listings ♦ Logics for complexity classes ♦ Parameterized complexity
Abstract Let C denote one of the complexity classes “polynomial time,” “logspace,” or “nondeterministic logspace.” We introduce a logic $L(C)_{inv}$ and show generalizations and variants of the equivalence $(L(C)_{inv}$ captures C if and only if there is an almost C-optimal algorithm in C for the set Taut of tautologies of propositional logic). These statements are also equivalent to the existence of a listing of subsets in C of Taut by corresponding Turing machines and equivalent to the fact that a certain parameterized halting problem is in the parameterized complexity class $XC_{uni}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-08-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 59
Issue Number 4
Page Count 34
Starting Page 1
Ending Page 34

Open content in new tab

   Open content in new tab
Source: ACM Digital Library