Some consequences of non-uniform conditions on uniform classes
From MaRDI portal
(Redirected from Publication:794427)
Recommendations
Cites work
- scientific article; zbMATH DE number 3594673 (Why is no real title available?)
- A Note on Sparse Complete Sets
- A comparison of polynomial time reducibilities
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- The polynomial-time hierarchy
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
Cited in
(84)- The 1-Versus-2 Queries Problem Revisited
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
- Commutative queries
- Lower bounds for kernelizations and other preprocessing procedures
- Improving known solutions is hard
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- Is intractability of nonmonotonic reasoning a real drawback?
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Fine-grained complexity of safety verification
- On the power of two-local random reductions
- The size of a revised knowledge base
- The 1-versus-2 queries problem revisited
- What's next? Future directions in parameterized complexity
- scientific article; zbMATH DE number 7651202 (Why is no real title available?)
- Infeasibility of instance compression and succinct PCPs for NP
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Instruction sequence based non-uniform complexity classes
- Towards non-black-box separations of public key encryption and one way function
- A uniform approach to define complexity classes
- On compact representations of propositional circumscription
- Some connections between bounded query classes and non-uniform complexity.
- FPT and kernelization algorithms for the induced tree problem
- Two edge modification problems without polynomial kernels
- Sparse sets, approximable sets, and parallel queries to NP
- Parameterized complexity of Eulerian deletion problems
- Logarithmic advice classes
- On sparse hard sets for counting classes
- The Boolean hierarchy of NP-partitions
- New developments in structural complexity theory
- Complexity theory basics: NP and NL
- scientific article; zbMATH DE number 1555980 (Why is no real title available?)
- Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints
- New collapse consequences of NP having small circuits
- Dual parameterization of weighted coloring
- On nonadaptive reductions to the set of random strings and its dense subsets
- Reductions to sets of low information content (extended abstract)
- Dual parameterization of weighted coloring
- Lower bounds on kernelization
- scientific article; zbMATH DE number 4081538 (Why is no real title available?)
- Parameterized complexity of Eulerian deletion problems
- On some natural complete operators
- scientific article; zbMATH DE number 7758317 (Why is no real title available?)
- Two queries
- Data reduction for graph coloring problems
- Two edge modification problems without polynomial kernels
- What Is Known About Vertex Cover Kernelization?
- Data reduction for graph coloring problems
- Multistage vertex cover
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- scientific article; zbMATH DE number 4100610 (Why is no real title available?)
- scientific article; zbMATH DE number 4090801 (Why is no real title available?)
- On cutwidth parameterized by vertex cover
- New limits to classical and quantum instance compression
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- scientific article; zbMATH DE number 7561499 (Why is no real title available?)
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- On the complexity of ranking
- Backdoors to tractable answer set programming
- Nonuniform lowness and strong nonuniform lowness
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- A completeness theory for polynomial (Turing) kernelization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Competing provers yield improved Karp-Lipton collapse results
- On hiding information from an oracle
- Preprocessing of intractable problems
- Separating NE from some nonuniform nondeterministic complexity classes
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Graph isomorphism is in the low hierarchy
- Exact and parameterized algorithms for read-once refutations in Horn constraint systems
- Probabilistic complexity classes and lowness
- On small generators
- Monotonous and randomized reductions to sparse sets
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- Tree-like unit refutations in Horn constraint systems
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- Bounded queries, approximations, and the Boolean hierarchy
- Clique Cover and Graph Separation
- On the Complexity of Bounded Context Switching.
- On the approximability of path and cycle problems in arc-dependent networks
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- An information-theoretic treatment of random-self-reducibility (extended abstract)
This page was built for publication: Some consequences of non-uniform conditions on uniform classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794427)
