Pages that link to "Item:Q4139688"
From MaRDI portal
The following pages link to Satisfiability Is Quasilinear Complete in NQL (Q4139688):
Displaying 20 items.
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- Shorter arithmetization of nondeterministic computations (Q496013) (← links)
- Observations on complete sets between linear time and polynomial time (Q627129) (← 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)
- Short propositional formulas represent nondeterministic computations (Q1096390) (← links)
- Invariance properties of RAMs and linear time (Q1327595) (← links)
- On parallel hierarchies and \(R_k^i\) (Q1377627) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval (Q1589441) (← 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)
- Data independence of read, write, and control structures in PRAM computations (Q1975968) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Local Reductions (Q3448833) (← links)
- Linear time transformations between combinatorial problems (Q3936214) (← links)
- Algebraic and logical characterizations of deterministic linear time classes (Q5048946) (← links)
- Power indices and easier hard problems (Q5751941) (← links)
- Effective guessing has unlikely consequences (Q6109068) (← links)
