The following pages link to The polynomial-time hierarchy (Q1236109):
Displaying 50 items.
- Quantifier reordering for QBF (Q287386) (← links)
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP (Q293222) (← 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)
- Motion planning with pulley, rope, and baskets (Q385498) (← links)
- Semantic query optimization in the presence of types (Q389237) (← links)
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking (Q395003) (← links)
- Bilevel programming and the separation problem (Q403662) (← links)
- Lower complexity bounds in justification logic (Q408543) (← links)
- Model-checking hierarchical structures (Q414908) (← links)
- Deciding safety properties in infinite-state pi-calculus via behavioural types (Q418155) (← links)
- Pinpointing the complexity of the interval min-max regret knapsack problem (Q429656) (← links)
- A complex analogue of Toda's theorem (Q454132) (← links)
- The consequences of eliminating NP solutions (Q458458) (← links)
- Second-order propositional modal logic and monadic alternation hierarchies (Q466445) (← links)
- Circuit lower bounds in bounded arithmetics (Q466447) (← links)
- Practical algorithms for MSO model-checking on tree-decomposable graphs (Q473216) (← links)
- Analyzing restricted fragments of the theory of linear arithmetic (Q513354) (← links)
- The complexity of counting quantifiers on equality languages (Q515549) (← links)
- Computational complexity of finite asynchronous cellular automata (Q517039) (← links)
- Path-disruption games: bribery and a probabilistic model (Q519896) (← links)
- Graph editing problems with extended regularity constraints (Q526874) (← links)
- Querying logical databases (Q579967) (← links)
- The strong exponential hierarchy collapses (Q584250) (← links)
- Graph properties checkable in linear time in the number of vertices (Q596315) (← links)
- The most nonelementary theory (Q598194) (← links)
- Algorithmic uses of the Feferman-Vaught theorem (Q598280) (← links)
- The complexity of computing the permanent (Q600247) (← links)
- Extensions of MSO and the monadic counting hierarchy (Q617710) (← links)
- The complexity of Boolean formula minimization (Q619911) (← links)
- Observations on complete sets between linear time and polynomial time (Q627129) (← links)
- Verification in incomplete argumentation frameworks (Q668774) (← links)
- On adaptive DLOGTIME and POLYLOGTIME reductions (Q672322) (← links)
- On the acceptance power of regular languages (Q672323) (← links)
- On quasilinear-time complexity theory (Q672330) (← links)
- A note on P-selective sets and closeness (Q673619) (← links)
- Methods for proving completeness via logical reductions (Q685391) (← links)
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) (← links)
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory (Q685716) (← links)
- Arithmetization: A new method in structural complexity theory (Q685721) (← links)
- On the complexity of queries in the logical data model (Q688665) (← links)
- The complexity of almost linear diophantine problems (Q753494) (← links)
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories (Q793017) (← links)
- Some consequences of non-uniform conditions on uniform classes (Q794427) (← links)
- The complexity of two-player games of incomplete information (Q800838) (← links)
- On small generators (Q802309) (← links)
- On the complexity of counting in the polynomial hierarchy (Q808260) (← links)
- Pseudorandom bits for constant depth circuits (Q808707) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- Simple sentences that are hard to decide (Q810009) (← links)
