The following pages link to (Q3826533):
Displayed 23 items.
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- Combinatorial PCPs with efficient verifiers (Q483706) (← links)
- Shorter arithmetization of nondeterministic computations (Q496013) (← links)
- Graph properties checkable in linear time in the number of vertices (Q596315) (← links)
- On quasilinear-time complexity theory (Q672330) (← links)
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness (Q673091) (← links)
- Invariance properties of RAMs and linear time (Q1327595) (← links)
- A descriptive complexity approach to the linear hierarchy. (Q1401413) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- Lower bounds on the complexity of recognizing SAT by Turing machines (Q1603493) (← links)
- Local reduction (Q1641001) (← links)
- Sorting, linear time and the satisfiability problem (Q1817067) (← links)
- Nonerasing, counting, and majority over the linear time hierarchy (Q1854524) (← links)
- Computing absolutely normal numbers in nearly linear time (Q2051782) (← links)
- Linear-size constant-query IOPs for delegating computation (Q2175951) (← links)
- Constrained synchronization and commutativity (Q2235741) (← links)
- Real-time computability of real numbers by chemical reaction networks (Q2400944) (← links)
- Time polynomial in input or output (Q3033752) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Local Reductions (Q3448833) (← links)
- Algebraic and logical characterizations of deterministic linear time classes (Q5048946) (← links)
- Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program (Q5231683) (← links)
- Computation models and function algebras (Q6064278) (← links)