Pages that link to "Item:Q4109299"

The following pages link to Relativization of questions about log space computability (Q4109299):

Displayed 44 items.

• On quasilinear-time complexity theory (Q672330) ‎ (← links)
• Computing functions with parallel queries to NP (Q673784) ‎ (← links)
• Planar and grid graph reachability problems (Q733742) ‎ (← links)
• New developments in structural complexity theory (Q913509) ‎ (← links)
• On the autoreducibility of functions (Q970103) ‎ (← links)
• Consistency in nondeterministic storage (Q1060847) ‎ (← links)
• Space-bounded hierarchies and probabilistic computations (Q1062759) ‎ (← links)
• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) (Q1094139) ‎ (← links)
• More complicated questions about maxima and minima, and some closures of NP (Q1107524) ‎ (← links)
• Decompositions of nondeterministic reductions (Q1108263) ‎ (← links)
• Relativized alternation and space-bounded computation (Q1111024) ‎ (← links)
• A measure of relativized space which is faithful with respect to depth (Q1115190) ‎ (← links)
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) (Q1118407) ‎ (← links)
• Some results on relativized deterministic and nondeterministic time hierarchies (Q1162808) ‎ (← links)
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space (Q1168735) ‎ (← links)
• On truth-table reducibility to SAT (Q1173957) ‎ (← links)
• An NL hierarchy (Q1182111) ‎ (← links)
• A survey of space complexity (Q1193412) ‎ (← links)
• Diagonalization, uniformity, and fixed-point theorems (Q1201287) ‎ (← links)
• A very hard log-space counting class (Q1208403) ‎ (← links)
• Log space machines with multiple oracle tapes (Q1242686) ‎ (← links)
• On languages specified by relative acceptance (Q1249438) ‎ (← links)
• Succinctness as a source of complexity in logical formalisms (Q1302307) ‎ (← links)
• The relative power of logspace and polynomial time reductions (Q1312179) ‎ (← links)
• Census techniques collapse space classes (Q1332770) ‎ (← links)
• Space-efficient recognition of sparse self-reducible languages (Q1337147) ‎ (← links)
• On the reducibility of sets inside NP to sets with low information content (Q1765294) ‎ (← links)
• On the complexity of data disjunctions. (Q1853503) ‎ (← links)
• Alternating and empty alternating auxiliary stack automata. (Q1874397) ‎ (← links)
• Space-efficient informational redundancy (Q1959428) ‎ (← links)
• Complexity theory for splicing systems (Q2455600) ‎ (← links)
• Positive relativizations for log space computability (Q2639638) ‎ (← links)
• A note on relativized log space (Q3036705) ‎ (← links)
• Parity, circuits, and the polynomial-time hierarchy (Q3318683) ‎ (← links)
• RelativizedNC (Q3763591) ‎ (← links)
• On relativizing auxiliary pushdown machines (Q3862402) ‎ (← links)
• Completeness for nondeterministic complexity classes (Q3979608) ‎ (← links)
• A time-space hierarchy between polynomial time and polynomial space (Q4000863) ‎ (← links)
• Structure and importance of logspace-MOD class (Q4009813) ‎ (← links)
• Generalized theorems on relationships among reducibility notions to certain complexity classes (Q4298368) ‎ (← links)
• On the complexity of graph reconstruction (Q4298372) ‎ (← links)
• Adaptive logspace reducibility and parallel time (Q4327383) ‎ (← links)
• Relativized logspace and generalized quantifiers over finite ordered structures (Q4358054) ‎ (← links)
• Relationships among $PL$, $\#L$, and the determinant (Q4889814) ‎ (← links)