Some consequences of non-uniform conditions on uniform classes
From MaRDI portal
Publication:794427
DOI10.1016/0304-3975(83)90020-8zbMATH Open0541.68017OpenAlexW1986602165MaRDI QIDQ794427FDOQ794427
Authors: Chee K. Yap 
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90020-8
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- The polynomial-time hierarchy
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- A comparison of polynomial time reducibilities
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Title not available (Why is that?)
Cited In (86)
- Lower bounds for kernelizations and other preprocessing procedures
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes
- Improving known solutions is hard
- Fine-grained complexity of safety verification
- \(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
- On the power of two-local random reductions
- The size of a revised knowledge base
- On sparsification for computing treewidth
- The 1-versus-2 queries problem revisited
- What's next? Future directions in parameterized complexity
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Infeasibility of instance compression and succinct PCPs for NP
- Towards non-black-box separations of public key encryption and one way function
- A uniform approach to define complexity classes
- FPT and kernelization algorithms for the induced tree problem
- Two edge modification problems without polynomial kernels
- On compact representations of propositional circumscription
- Some connections between bounded query classes and non-uniform complexity.
- 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
- Title not available (Why is that?)
- New collapse consequences of NP having small circuits
- Reductions to sets of low information content (extended abstract)
- Dual parameterization of weighted coloring
- Dual parameterization of weighted coloring
- Title not available (Why is that?)
- Parameterized complexity of Eulerian deletion problems
- Lower bounds on kernelization
- On some natural complete operators
- Two queries
- Two edge modification problems without polynomial kernels
- Data reduction for graph coloring problems
- Data reduction for graph coloring problems
- Multistage vertex cover
- Title not available (Why is that?)
- Title not available (Why is that?)
- New limits to classical and quantum instance compression
- On cutwidth parameterized by vertex cover
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Backdoors to tractable answer set programming
- A completeness theory for polynomial (Turing) kernelization
- Nonuniform lowness and strong nonuniform lowness
- On the complexity of ranking
- Competing provers yield improved Karp-Lipton collapse results
- Preprocessing of intractable problems
- On hiding information from an oracle
- Separating NE from some nonuniform nondeterministic complexity classes
- Graph isomorphism is in the low hierarchy
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Probabilistic complexity classes and lowness
- Monotonous and randomized reductions to sparse sets
- On small generators
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- On the approximability of path and cycle problems in arc-dependent networks
- On the Complexity of Bounded Context Switching.
- Clique Cover and Graph Separation
- Bounded queries, approximations, and the Boolean hierarchy
- 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
- Turing kernelization for finding long paths and cycles in restricted graph classes
- The 1-Versus-2 Queries Problem Revisited
- Commutative queries
- Title not available (Why is that?)
- Instruction sequence based non-uniform complexity classes
- Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints
- Complexity theory basics: NP and NL
- On nonadaptive reductions to the set of random strings and its dense subsets
- Title not available (Why is that?)
- What Is Known About Vertex Cover Kernelization?
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- Title not available (Why is that?)
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Exact and parameterized algorithms for read-once refutations in Horn constraint systems
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- Tree-like unit refutations in Horn constraint systems
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
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)
