A novel characterization of the complexity class Θ2P based on counting and comparison
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...
| Autori principali: | , |
|---|---|
| Natura: | Journal article |
| Pubblicazione: |
Elsevier
2017
|