Pages that link to "Item:Q794427"
From MaRDI portal
The following pages link to Some consequences of non-uniform conditions on uniform classes (Q794427):
Displaying 50 items.
- Sparse sets, approximable sets, and parallel queries to NP (Q294651) (← links)
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter (Q372970) (← links)
- Data reduction for graph coloring problems (Q393081) (← links)
- Lower bounds on kernelization (Q456702) (← links)
- On cutwidth parameterized by vertex cover (Q476444) (← links)
- Lower bounds for kernelizations and other preprocessing procedures (Q538466) (← links)
- Infeasibility of instance compression and succinct PCPs for NP (Q619903) (← links)
- Improving known solutions is hard (Q687508) (← links)
- Turing kernelization for finding long paths and cycles in restricted graph classes (Q730497) (← links)
- Dual parameterization of weighted coloring (Q786042) (← links)
- On small generators (Q802309) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP (Q908700) (← links)
- New developments in structural complexity theory (Q913509) (← links)
- On the complexity of ranking (Q920620) (← links)
- The Boolean hierarchy of NP-partitions (Q924719) (← links)
- The 1-versus-2 queries problem revisited (Q970102) (← links)
- On some natural complete operators (Q1064780) (← links)
- Graph isomorphism is in the low hierarchy (Q1116696) (← links)
- Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170) (← links)
- Logarithmic advice classes (Q1193903) (← links)
- On the power of two-local random reductions (Q1209364) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- On hiding information from an oracle (Q1263281) (← links)
- Probabilistic complexity classes and lowness (Q1263979) (← links)
- On compact representations of propositional circumscription (Q1391128) (← links)
- Is intractability of nonmonotonic reasoning a real drawback? (Q1391905) (← links)
- Some connections between bounded query classes and non-uniform complexity. (Q1426008) (← links)
- Two edge modification problems without polynomial kernels (Q1662097) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- Commutative queries (Q1854422) (← links)
- Bounded queries, approximations, and the Boolean hierarchy (Q1854449) (← links)
- Preprocessing of intractable problems (Q1854544) (← links)
- Nonuniform lowness and strong nonuniform lowness (Q1894328) (← links)
- Two queries (Q1961371) (← links)
- The size of a revised knowledge base (Q1978467) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization (Q2032346) (← links)
- On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems (Q2049975) (← links)
- Multistage vertex cover (Q2135630) (← links)
- Exact and parameterized algorithms for read-once refutations in Horn constraint systems (Q2151419) (← links)
- Tree-like unit refutations in Horn constraint systems (Q2232285) (← links)
- Backdoors to tractable answer set programming (Q2341833) (← links)
- A completeness theory for polynomial (Turing) kernelization (Q2343083) (← links)
- On sparsification for computing treewidth (Q2343087) (← links)
- Parameterized complexity of Eulerian deletion problems (Q2441593) (← links)
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy (Q2456368) (← links)
- FPT and kernelization algorithms for the induced tree problem (Q2692722) (← links)
- Complexity Theory Basics: NP and NL (Q2821692) (← links)
- FPT is characterized by useful obstruction sets (Q2828222) (← links)
