Journal article icon

Journal article

A novel characterization of the complexity class Θ2P based on counting and comparison

Abstract:

The complexity class Θ2P, which is the class of languages recognizable by deterministic Turing machines in polynomial time with at most logarithmic many calls to an NP oracle, received extensive attention in the literature. Its complete problems can be characterized by different specific tasks, such as deciding whether the optimum solution of an NP problem is unique, or whether it is in some sense “odd” (e.g., whether its size is an odd number). In this paper, we introduce a new characterizat...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2017.06.023

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
More by this author
Department:
Oxford, MPLS, Computer Science
Publisher:
Elsevier Publisher's website
Journal:
Theoretical Computer Science Journal website
Volume:
694
Pages:
21-33
Publication date:
2017-07-08
Acceptance date:
2017-06-28
DOI:
ISSN:
0304-3975
Pubs id:
pubs:709305
URN:
uri:2c526033-320d-419b-a88c-6a593a4ae23b
UUID:
uuid:2c526033-320d-419b-a88c-6a593a4ae23b
Local pid:
pubs:709305

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP