Some consequences of non-uniform conditions on uniform classes

DOI10.1016/0304-3975(83)90020-8zbMath0541.68017OpenAlexW1986602165MaRDI QIDQ794427

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

zbMATH Keywords

Meyer-Stockmeyer hierarchy Non-uniform complexity classes sparse complete sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (77)

Sparse sets, approximable sets, and parallel queries to NP ⋮ Multistage vertex cover ⋮ An information-theoretic treatment of random-self-reducibility ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Exact and parameterized algorithms for read-once refutations in Horn constraint systems ⋮ Two edge modification problems without polynomial kernels ⋮ Graph isomorphism is in the low hierarchy ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Clique Cover and Graph Separation ⋮ Data reduction for graph coloring problems ⋮ On compact representations of propositional circumscription ⋮ Is intractability of nonmonotonic reasoning a real drawback? ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ On the approximability of path and cycle problems in arc-dependent networks ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Unnamed Item ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ New developments in structural complexity theory ⋮ Unnamed Item ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Lower bounds on kernelization ⋮ On the complexity of ranking ⋮ Two queries ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ The Boolean hierarchy of NP-partitions ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ On cutwidth parameterized by vertex cover ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Tree-like unit refutations in Horn constraint systems ⋮ The size of a revised knowledge base ⋮ Dual parameterization of Weighted Coloring ⋮ New collapse consequences of NP having small circuits ⋮ Logarithmic advice classes ⋮ Improving known solutions is hard ⋮ Lower bounds for kernelizations and other preprocessing procedures ⋮ On the power of two-local random reductions ⋮ On sparse hard sets for counting classes ⋮ The 1-versus-2 queries problem revisited ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Unnamed Item ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Reductions to sets of low information content ⋮ Fine-grained complexity of safety verification ⋮ On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems ⋮ On hiding information from an oracle ⋮ Probabilistic complexity classes and lowness ⋮ Data Reduction for Graph Coloring Problems ⋮ Complexity Theory Basics: NP and NL ⋮ Monotonous and randomized reductions to sparse sets ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ FPT is characterized by useful obstruction sets ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ On the Complexity of Bounded Context Switching. ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Dual parameterization of weighted coloring ⋮ Backdoors to tractable answer set programming ⋮ Unnamed Item ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ Preprocessing of intractable problems ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On sparsification for computing treewidth ⋮ On small generators ⋮ On some natural complete operators ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

Cites Work

This page was built for publication: Some consequences of non-uniform conditions on uniform classes