The following pages link to On uniformity within \(NC^ 1\) (Q2640342):
Displaying 50 items.
- Relativizing small complexity classes and their theories (Q260396) (← links)
- The complexity of intersecting finite automata having few final states (Q347114) (← links)
- Resource trade-offs in syntactically multilinear arithmetic circuits (Q371194) (← links)
- Linear circuits, two-variable logic and weakly blocked monoids (Q391307) (← links)
- Model-checking hierarchical structures (Q414908) (← links)
- Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
- On uniformity and circuit lower bounds (Q488049) (← links)
- The complexity of counting quantifiers on equality languages (Q515549) (← links)
- The computational power of membrane systems under tight uniformity conditions (Q537860) (← links)
- Descriptional and computational complexity of finite automata -- a survey (Q553312) (← links)
- Extensions of MSO and the monadic counting hierarchy (Q617710) (← links)
- The isomorphism conjecture for constant depth reductions (Q619896) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- The expressiveness of a family of finite set languages (Q672126) (← links)
- On adaptive DLOGTIME and POLYLOGTIME reductions (Q672322) (← links)
- Computing with infinitary logic (Q672337) (← links)
- On input read-modes of alternating Turing machines (Q672377) (← links)
- Methods for proving completeness via logical reductions (Q685391) (← links)
- \(NC^ 1\): The automata-theoretic viewpoint (Q685708) (← links)
- Root finding with threshold circuits (Q690451) (← links)
- First-order logics: some characterizations and closure properties (Q715044) (← links)
- The exact complexity of projective image matching (Q736619) (← links)
- The parallel complexity of two problems on concurrency (Q811123) (← links)
- The equivalence of theories that characterize ALogTime (Q834715) (← links)
- Reductions to graph isomorphism (Q987394) (← links)
- The complexity of solitaire (Q1034532) (← links)
- Rudimentary reductions revisited (Q1183444) (← links)
- The graph of multiplication is equivalent to counting (Q1190513) (← links)
- The invariant problem for binary string structures and the parallel complexity theory of queries (Q1191022) (← links)
- Regular languages in \(NC\) (Q1191027) (← links)
- Deciding bisimilarity is P-complete (Q1203120) (← links)
- An optimal lower bound on the number of variables for graph identification (Q1204528) (← links)
- Extensions to Barrington's M-program model (Q1208406) (← links)
- A constant-space sequential model of computation for first-order logic (Q1271562) (← links)
- Succinct representation, leaf languages, and projection reductions (Q1271623) (← links)
- Relating polynomial time to constant depth (Q1274992) (← links)
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem (Q1276160) (← links)
- Nondeterministic \(NC^1\) computation (Q1276170) (← links)
- On the power of built-in relations in certain classes of program schemes (Q1277684) (← links)
- Context-sensitive transitive closure operators (Q1319508) (← links)
- The complexity of computing maximal word functions (Q1321032) (← links)
- On the language of primitive words (Q1351946) (← links)
- Expressing uniformity via oracles (Q1361886) (← links)
- Counting quantifiers, successor relations, and logarithmic space (Q1362332) (← links)
- A query language for NC (Q1376409) (← links)
- The complexity of the evaluation of complex algebra expressions (Q1376410) (← links)
- Gap-languages and log-time complexity classes (Q1389651) (← links)
- Expressive power of SQL. (Q1401278) (← links)
- The dynamic complexity of transitive closure is in DynTC\(^{0}\). (Q1401284) (← links)
- Completeness results for graph isomorphism. (Q1401960) (← links)