Tally languages and complexity classes

Cited in

(43)

On the computational complexity of membrane systems
Reductions on NP and p-selective sets
On random reductions from sparse sets to tally sets
The complexity of generating test instances
A downward translation in the polynomial hierarchy
Some observations on NP real numbers and P-selective sets
Relations among parallel and sequential computation models
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
Limitations of the upward separation technique
A positive relativization of polynomial time versus polylog space
NL-printable sets and nondeterministic Kolmogorov complexity
One-way permutations and self-witnessing languages
Tally NP sets and easy census functions.
Proof systems that take advice
On intractability of the classUP
On being incoherent without being very hard
Upward separations and weaker hypotheses in resource-bounded measure
Classes of bounded nondeterminism
Sparse sets and collapse of complexity classes
On the polynomial IO-complexity
Optimal proof systems imply complete sets for promise classes
Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
Logarithmic advice classes
Cook versus Karp-Levin: Separating completeness notions if NP is not small
Cellular automata: communication matters
On sparse sets in NP-P
Tradeoff lower lounds for stack machines
Computation times of NP sets of different densities
Average-case intractability vs. worst-case intractability
Locating P/poly optimally in the extended low hierarchy
A Downward Collapse within the Polynomial Hierarchy
Input-oblivious proof systems and a uniform complexity perspective on P/poly
Inclusion complete tally languages and the Hartmanis-Berman conjecture
Downward translations of equality
Language classes defined by time-bounded relativised cellular automata
A result relating disjunctive self-reducibility to P-immunity
Relations between average-case and worst-case complexity
Minimal pairs for P
On the definitions of some complexity classes of real numbers
NL-printable sets and nondeterministic Kolmogorov complexity
Reductions between disjoint NP-pairs
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
A note on P-selective sets and closeness

This page was built for publication: Tally languages and complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4775472)