Pages that link to "Item:Q3711749"

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

Displaying 44 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)