Pages that link to "Item:Q4191603"
From MaRDI portal
The following pages link to Relations Among Complexity Measures (Q4191603):
Displayed 50 items.
- Combinatorial PCPs with short proofs (Q260390) (← links)
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- Shorter arithmetization of nondeterministic computations (Q496013) (← links)
- Complexity of multi-head finite automata: origins and directions (Q616495) (← links)
- On quasilinear-time complexity theory (Q672330) (← links)
- On the power of several queues (Q685436) (← links)
- Linear speed-up does not hold on Turing machines with tree storages (Q688445) (← links)
- Improved simulation of nondeterministic Turing machines (Q764330) (← links)
- Bandwidth constraints on problems complete for polynomial time (Q791316) (← links)
- Characterization of all optimal networks for a simultaneous computation of AND and NOR (Q796492) (← links)
- On the computational complexity of qualitative coalitional games (Q814613) (← links)
- What is a sorting function? (Q843213) (← links)
- The complexity of depth-3 circuits computing symmetric Boolean functions (Q845823) (← links)
- Checking the correctness of memories (Q890427) (← links)
- Parallel models of computation: An introductory survey (Q916358) (← links)
- The complexity of deciding reachability properties of distributed negotiation schemes (Q924139) (← links)
- Complexity lower bounds for machine computing models (Q1057651) (← links)
- Uncontrollable computational growth in theoretical physics (Q1071512) (← links)
- Short propositional formulas represent nondeterministic computations (Q1096390) (← links)
- Optimal dynamic embedding of X-trees into arrays (Q1105377) (← links)
- A new complete language for DSPACE(log n) (Q1123607) (← links)
- Data encodings and their costs (Q1139942) (← links)
- On alternation (Q1141480) (← links)
- On uniform circuit complexity (Q1152951) (← links)
- On time versus space. II (Q1152954) (← links)
- An information-theoretic approach to time bounds for on-line computation (Q1156484) (← links)
- On the complexity of 2-output Boolean networks (Q1159183) (← links)
- Simulations among multidimensional Turing machines (Q1165001) (← links)
- A fast implementation of a multidimensional storage into a tree storage (Q1166931) (← links)
- Generic oracles, uniform machines, and codes (Q1184732) (← links)
- Extensions to Barrington's M-program model (Q1208406) (← links)
- Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines (Q1323339) (← links)
- Speedup of determinism by alternation for multidimensional Turing machines (Q1341727) (← links)
- On the simulation of many storage heads by one (Q1348528) (← links)
- On the simulation of quantum Turing machines. (Q1401393) (← links)
- Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. (Q1401920) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- Multi-head finite automata: Data-independent versus data-dependent computations (Q1608894) (← links)
- A simple construction of iO for Turing machines (Q1631340) (← links)
- Local reduction (Q1641001) (← links)
- Perennial secure multi-party computation of universal Turing machine (Q1737594) (← links)
- The size and depth of layered Boolean circuits (Q1944075) (← links)
- Constant-round maliciously secure two-party computation in the RAM model (Q2010585) (← links)
- On some FPT problems without polynomial Turing compressions (Q2072079) (← links)
- PAC-learning gains of Turing machines over circuits and neural networks (Q2111729) (← links)
- Adaptively secure computation for RAM programs (Q2170045) (← links)
- Tight hierarchy of data-independent multi-head automata (Q2194865) (← links)
- Oblivious two-way finite automata: decidability and complexity (Q2252534) (← links)
- A survey on temporal logics for specifying and verifying real-time systems (Q2418645) (← links)
- The complexity of contract negotiation (Q2457671) (← links)