Pages that link to "Item:Q3783278"

The following pages link to The difference and truth-table hierarchies for NP (Q3783278):

Displaying 46 items.

• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP (Q293222) (← links)
• Efficient algorithms for membership in Boolean hierarchies of regular languages (Q306282) (← links)
• Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games (Q314437) (← links)
• The complexity of computing minimal unidirectional covering sets (Q372959) (← links)
• Mind change speed-up for learning languages from positive data (Q388110) (← links)
• Fine hierarchies via Priestley duality (Q424549) (← links)
• The strong exponential hierarchy collapses (Q584250) (← links)
• Probabilistic polynomial time is closed under parity reductions (Q751270) (← links)
• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) (Q764326) (← links)
• On adaptive versus nonadaptive bounded query machines (Q808242) (← links)
• The Boolean hierarchy of NP-partitions (Q924719) (← links)
• Fine hierarchies and m-reducibilities in theoretical computer science (Q949621) (← links)
• The complexity of unions of disjoint sets (Q955349) (← links)
• Exact complexity of exact-four-colorability (Q1014384) (← links)
• Polynomial terse sets (Q1104077) (← links)
• Bounded query classes and the difference hierarchy (Q1114678) (← links)
• On truth-table reducibility to SAT (Q1173957) (← links)
• Bounded queries to SAT and the Boolean hierarchy (Q1178690) (← links)
• The structure of logarithmic advice complexity classes (Q1275000) (← links)
• A taxonomy of complexity classes of functions (Q1329166) (← links)
• Optimal series-parallel trade-offs for reducing a function to its own graph (Q1854508) (← links)
• Nondeterministic and randomized Boolean hierarchies in communication complexity (Q2041245) (← links)
• Emptiness problems for integer circuits (Q2182324) (← links)
• Acceptance in incomplete argumentation frameworks (Q2238645) (← links)
• Error-bounded probabilistic computations between MA and AM (Q2507698) (← links)
• A note on parallel queries and the symmetric-difference hierarchy. (Q2583533) (← links)
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP (Q3374757) (← links)
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES (Q3538855) (← links)
• A Downward Collapse within the Polynomial Hierarchy (Q4210153) (← links)
• Query Order (Q4210168) (← links)
• Generalized theorems on relationships among reducibility notions to certain complexity classes (Q4298368) (← links)
• Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP (Q4571954) (← links)
• A Survey on Difference Hierarchies of Regular Languages (Q4637687) (← links)
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ (Q4717047) (← links)
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies (Q4800264) (← links)
• On computing Boolean connectives of characteristic functions (Q4835862) (← links)
• Upper bounds for the complexity of sparse and tally descriptions (Q4864446) (← links)
• A downward translation in the polynomial hierarchy (Q5048934) (← links)
• Query order in the polynomial hierarchy (Q5055937) (← links)
• Characterizations of some complexity classes between Θ2p and Δ2p (Q5096790) (← links)
• Emptiness Problems for Integer Circuits (Q5111247) (← links)
• The Complexity Landscape of Outcome Determination in Judgment Aggregation (Q5139591) (← links)
• A relationship between difference hierarchies and relativized polynomial hierarchies (Q5289273) (← links)
• On the power of parity polynomial time (Q5750401) (← links)
• On boolean lowness and boolean highness (Q5941441) (← links)
• Intersection suffices for Boolean hierarchy equivalence (Q6085737) (← links)