Tally languages and complexity classes

Cited in

(43)

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

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)