Complete Sets and the Polynomial-Time Hierarchy

No abstract is available for this paper.

• Publication year

  1976

• Venue

  Theoretical Computer Science

• Publication date

  1976-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0304-3975(76)90062-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Polynomial-Time Hierarchy

  1976cited by this paper
• Space-Bounded Reducibility among Combinatorial Problems

  1975cited by this paper
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

  1975cited by this paper
• Thirteenth annual IEEE Symposium on switching and automata theory

  1974cited by this paper
• NONDETERMINISTIC TIME AND SPACE COMPLEXITY CLASSES

  1974cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Word problems requiring exponential time(Preliminary Report)

  1973cited by this paper
• The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

  1972cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• RELATIVIZATION OF THE THEORY OF COMPUTATION COMPLEXITY

  1972cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper
• Time- and Tape-Bounded Turing Acceptors and AFLs

  1970cited by this paper

• Higher Hardness Results for the Reconfiguration of Odd Matchings

  2026cites this paper
• Stackelberg Dynamic Location Planning under Cumulative Demand

  2026cites this paper
• A Note on the Complexity of Directed Clique

  2026cites this paper
• Facets in Argumentation: A Formal Approach to Argument Significance

  2025cites this paper
• A Note on the Complexity of Defensive Domination

  2025cites this paper
• Complexity of Faceted Explanations in Propositional Abduction

  2025cites this paper
• Efficient Rectification Signal Validation for Optimal Functional ECO Patch Generation

  2025cites this paper
• Counting and Reasoning with Plans

  2025cites this paper
• A Non-Interventionist Approach to Causal Reasoning based on Lewisian Counterfactuals

  2025cites this paper
• Cycle Patterns and Mean Payoff Games

  2025cites this paper
• Invariants for One-Counter Automata with Disequality Tests

  2024cites this paper
• On the Complexity of the Bilevel Shortest Path Problem

  2024cites this paper
• On the completeness of several fortification-interdiction games in the Polynomial Hierarchy

  2024cites this paper
• On the complexity of robust multi-stage problems with discrete recourse

  2024cites this paper
• Epistemic Logic Programs: Non-Ground and Counting Complexity

  2024cites this paper
• A SYSTEM OF INTERACTION AND STRUCTURE III: THE COMPLEXITY OF SYSTEM BV AND POMSET LOGIC

  2023cites this paper
• Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

  2023cites this paper
• Forall-exist statements in pseudopolynomial time

  2023cites this paper
• On counting propositional logic and Wagner's hierarchy

  2023cites this paper
• Towards logical foundations for probabilistic computation

  2023cites this paper
• Coefficient Synthesis for Threshold Automata

  2023cites this paper
• Complexity of the Multilvel Critical Node Problem

  2023cites this paper
• A SYSTEM OF INTERACTION AND STRUCTURE III: THE COMPLEXITY OF SYSTEM BV AND POMSET LOGIC

  2023cites this paper
• Efficient Interactive Proofs for Non-Deterministic Bounded Space

  2023cites this paper
• The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks

  2023cites this paper
• Feasibility analysis for HPC-DAG tasks

  2022influential citation
• Higher-Order Quantified Boolean Satisfiability

  2022cites this paper
• Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs

  2022cites this paper
• Energy Games with Resource-Bounded Environments

  2022cites this paper
• A System of Interaction and Structure III: The Complexity of BV and Pomset Logic

  2022cites this paper
• Handbook of Satisfiability

  2021cites this paper
• Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard

  2021cites this paper
• On the Complexity of Finding Justifications for Collective Decisions

  2021cites this paper
• Responsibility and verification: Importance value in temporal logics

  2021cites this paper
• COUNTING HIERARCHIES(cid:2) POLYNOMIAL TIME AND CONSTANT DEPTH CIRCUITS

  2021cites this paper
• On Counting Propositional Logic and Wagner's Hierarchy

  2021cites this paper
• Partitioned Scheduling of Recurrent Real-Time Tasks

  2021cites this paper
• Feasibility Analysis of Conditional DAG Tasks

  2021cites this paper
• Complexity results for preference aggregation over (m)CP-nets: Max and rank voting

  2021influential citation
• Kemeny Consensus Complexity

  2021cites this paper
• Variational Quantum Optimization with Multi-Basis Encodings

  2021cites this paper
• Rushing and Strolling among Answer Sets - Navigation Made Easy

  2021cites this paper
• Complexity of the Multilevel Critical Node Problem

  2020influential citation
• Computational Complexity Characterization of Protecting Elections from Bribery

  2020influential citation
• High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

  2020cites this paper
• The Complexity Landscape of Outcome Determination in Judgment Aggregation

  2020cites this paper
• Explanations for Ontology-Mediated Query Answering in Description Logics (Extended Abstract)

  2020cites this paper
• Work in Progress: The ILP-Tractability of Schedulability Analysis Problems

  2020cites this paper
• Explanations for Query Answers under Existential Rules

  2019cites this paper
• A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

  2019influential citation
• Language Inclusion for Finite Prime Event Structures

  2019cites this paper
• Very Hard Electoral Control Problems

  2018cites this paper
• Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting

  2018cites this paper
• Protecting Election from Bribery: New Approach and Computational Complexity Characterization

  2018cites this paper
• Enhanced Unsatisfiable Cores for QBF: Weakening Universal to Existential Quantifiers

  2018cites this paper
• Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy

  2018cites this paper
• Decidability of the Regular Intersection Emptiness Problem

  2018cites this paper
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

  2018cites this paper
• Principles and Practice of Constraint Programming

  2018cites this paper
• More Complexity Results about Reasoning over ( m )CP-nets

  2018cites this paper
• A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions

  2018cites this paper
• Evaluating QBF Solvers: Quantifier Alternations Matter

  2017cites this paper
• Parameterized complexity classes beyond para-NP

  2017cites this paper
• On the Containment Problem for Linear Sets

  2017cites this paper
• On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances

  2017cites this paper
• Complexity Results for Aggregating Judgments using Scoring or Distance-Based Procedures

  2017cites this paper
• A novel characterization of the complexity class ϴPk based on counting and comparison

  2017cites this paper
• Graph Models for Rational Social Interaction

  2017cites this paper
• The Robustness of LWPP and WPP, with an Application to Graph Reconstruction

  2017cites this paper
• Understanding the complexity of axiom pinpointing in lightweight description logics

  2017cites this paper
• Complexity Results for Manipulation, Bribery and Control of the Kemeny Judgment Aggregation Procedure

  2017cites this paper
• Election-Attack Complexity for More Natural Models

  2017cites this paper
• Answer Set Solving using Tree Decompositions and Dynamic Programming — The DynASP 2 System — DBAI-TR-2016-101 , Revised Version

  2016cites this paper
• Complexity Results for Manipulation, Bribery and Control of the Kemeny Procedure in Judgment Aggregation

  2016cites this paper
• The Complexity of the Numerical Semigroup Gap Counting Problem

  2016influential citation
• The Computational Complexity of the Frobenius Problem

  2016cites this paper
• Beyond Intractability: A Computational Complexity Analysis of Various Types of Influence and Stability in Cooperative Games

  2016cites this paper
• Path-Disruption Games: Bribery and a Probabilistic Model

  2016cites this paper
• Complete Problems of Propositional Logic for the Exponential Hierarchy

  2016cites this paper
• An Overview of Non-Uniform Parameterized Complexity

  2015cites this paper
• Parameterized Complexity Results for Agenda Safety in Judgment Aggregation

  2015cites this paper
• Counting all possible simple paths using Artificial Cell division mechanism for directed acyclic graphs

  2015cites this paper
• Bidirectional Constraints for Exchanging Data: Beyond Monotone Queries

  2015cites this paper
• A casual semantics for Logic Programming

  2015cites this paper
• Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP

  2015influential citation
• Interactions and Complexity in Multi-Agent Justification Logic

  2015cites this paper
• Complexity Theory Column 89

  2015cites this paper
• Complexity of the Winner Determination Problem in Judgment Aggregation: Kemeny, Slater, Tideman, Young

  2015influential citation
• A Novel Boolean Expression based Algorithm to find all possible Simple Paths between two nodes of a Graph

  2014cites this paper
• Four-Valued Reasoning and Cyclic Circuits

  2014cites this paper
• Complexity theory in Feasible Mathematics

  2014cites this paper
• Lower bounds on the complexity of MSO1 model-checking

  2014cites this paper
• The Computational Complexity of Structure-Based Causality

  2014cites this paper
• Perfect correspondences between dot-depth and polynomial-time hierarchies

  2014cites this paper
• Practical algorithms for MSO model-checking on tree-decomposable graphs

  2014cites this paper
• Multiobjective Traveling Salesman Problems and Redundancy of Complete Sets (Mehrkriterielle Traveling Salesman Probleme und Redundanz vollständiger Mengen)

  2014cites this paper
• Complexity Theory

  2014cites this paper
• The Parameterized Complexity of Reasoning Problems Beyond NP

  2013influential citation
• Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

  2013cites this paper
• Circuit lower bounds in bounded arithmetics

  2013cites this paper