Pages that link to "Item:Q3711749"

The following pages link to Sparse sets in NP-P: EXPTIME versus NEXPTIME (Q3711749):

Displayed 45 items.

• On the polynomial IO-complexity (Q582102) ‎ (← links)
• The strong exponential hierarchy collapses (Q584250) ‎ (← links)
• Non-deterministic exponential time has two-prover interactive protocols (Q685724) ‎ (← links)
• Finite-model theory -- A personal perspective (Q688663) ‎ (← links)
• Avoiding simplicity is complex (Q693072) ‎ (← links)
• Kolmogorov characterizations of complexity classes (Q804291) ‎ (← links)
• New developments in structural complexity theory (Q913509) ‎ (← links)
• Downward translations of equality (Q914368) ‎ (← links)
• A result relating disjunctive self-reducibility to P-immunity (Q915447) ‎ (← links)
• 0-1 laws and decision problems for fragments of second-order logic (Q920075) ‎ (← links)
• On the complexity of ranking (Q920620) ‎ (← links)
• Bi-immunity results for cheatable sets (Q920981) ‎ (← links)
• On sets polynomially enumerable by iteration (Q1176233) ‎ (← links)
• The complexity of computing the number of strings of given length in context-free languages (Q1178713) ‎ (← links)
• Logarithmic advice classes (Q1193903) ‎ (← links)
• On being incoherent without being very hard (Q1198954) ‎ (← links)
• Polynomial-time compression (Q1198955) ‎ (← links)
• Exponential-time and subexponential-time sets (Q1261474) ‎ (← links)
• Bridging across the \(\log(n)\) space frontier (Q1271619) ‎ (← links)
• Succinctness as a source of complexity in logical formalisms (Q1302307) ‎ (← links)
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs (Q1321029) ‎ (← links)
• Space-efficient recognition of sparse self-reducible languages (Q1337147) ‎ (← links)
• A general method to construct oracles realizing given relationships between complexity classes (Q1351504) ‎ (← links)
• Separating classes in the exponential-time hierarchy from classes in PH (Q1365687) ‎ (← links)
• Optimal proof systems imply complete sets for promise classes (Q1398371) ‎ (← links)
• Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) ‎ (← links)
• The isoperimetric spectrum of finitely presented groups (Q1630589) ‎ (← links)
• On the reducibility of sets inside NP to sets with low information content (Q1765294) ‎ (← links)
• On the computational complexity of best Chebyshev approximations (Q1821775) ‎ (← links)
• Tally NP sets and easy census functions. (Q1854340) ‎ (← links)
• Sparse sets and collapse of complexity classes (Q1854459) ‎ (← links)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) ‎ (← links)
• NL-printable sets and nondeterministic Kolmogorov complexity (Q2369009) ‎ (← links)
• Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations (Q2693688) ‎ (← links)
• Reducibilities on tally and sparse sets (Q3357534) ‎ (← links)
• Limitations of the upward separation technique (Q3490941) ‎ (← links)
• A Downward Collapse within the Polynomial Hierarchy (Q4210153) ‎ (← links)
• Towards the Actual Relationship Between NP and Exponential Time (Q4238424) ‎ (← links)
• On the cutting edge of relativization: The resource bounded injury method (Q4632432) ‎ (← links)
• NL-printable sets and Nondeterministic Kolmogorov Complexity (Q4924524) ‎ (← links)
• A downward translation in the polynomial hierarchy (Q5048934) ‎ (← links)
• Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782) ‎ (← links)
• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) (Q5919539) ‎ (← links)
• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) (Q5920059) ‎ (← links)
• Binary coded unary regular languages (Q6199860) ‎ (← links)