Tally languages and complexity classes

Cited In (42)

On the computational complexity of membrane systems
The complexity of generating test instances
Reductions on NP and p-selective sets
On random reductions from sparse sets to tally sets
A downward translation in the polynomial hierarchy
Relations among parallel and sequential computation models
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
Some observations on NP real numbers and P-selective sets
Limitations of the upward separation technique
NL-printable sets and nondeterministic Kolmogorov complexity
A positive relativization of polynomial time versus polylog space
One-way permutations and self-witnessing languages
Tally NP sets and easy census functions.
On intractability of the classUP
Proof systems that take advice
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
Optimal proof systems imply complete sets for promise classes
On the polynomial IO-complexity
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
On sparse sets in NP-P
Computation times of NP sets of different densities
Tradeoff lower lounds for stack machines
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)