More complicated questions about maxima and minima, and some closures of NP
From MaRDI portal
Publication:1107524
DOI10.1016/0304-3975(87)90049-1zbMath0653.03027OpenAlexW2088044688MaRDI QIDQ1107524
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(87)90049-1
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (50)
Probabilistic logic under coherence: complexity and algorithms ⋮ Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ Efficient timed model checking for discrete-time systems ⋮ Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP ⋮ The operators min and max on the polynomial hierarchy ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ Random parallel algorithms for finding exact branchings, perfect matchings, and cycles ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ The complexity of online manipulation of sequential elections ⋮ Weighted Boolean Formula Games ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Controlling weighted voting games by deleting or adding players with or without changing the quota ⋮ Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ The complexity of computing minimal unidirectional covering sets ⋮ On the equivalence of distributed systems with queries and communication ⋮ On monotonous oracle machines ⋮ Toward credible belief base revision ⋮ Mixed Iterated Revisions: Rationale, Algorithms, and Complexity ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Taking into account ``who said what in abstract argumentation: complexity results ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Manipulation in communication structures of graph-restricted weighted voting games ⋮ Inconsistency-Tolerant Querying of Description Logic Knowledge Bases ⋮ Logical foundations of information disclosure in ontology-based data integration ⋮ Unnamed Item ⋮ The computational complexity of weak saddles ⋮ Optimal satisfiability for propositional calculi and constraint satisfaction problems. ⋮ On truth-table reducibility to SAT ⋮ Complexity of stability ⋮ Federation and Navigation in SPARQL 1.1 ⋮ Complexity of Stability. ⋮ Isomorphic implication ⋮ Query evaluation on a database given by a random graph ⋮ Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy ⋮ Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP ⋮ Exact complexity of exact-four-colorability ⋮ Deciding According to the Shortest Computations ⋮ Monotonous and randomized reductions to sparse sets ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ Finding Optimal Solutions With Neighborly Help. ⋮ THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY ⋮ Complexity results for structure-based causality. ⋮ A note on parallel queries and the symmetric-difference hierarchy. ⋮ The minimum equivalent DNF problem and shortest implicants ⋮ \(\text{DA}^2\) merging operators ⋮ The complexity of Kemeny elections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- The complexity of combinatorial problems with succinct input representation
- A comparison of polynomial time reducibilities
- Some simplified NP-complete graph problems
- The polynomial-time hierarchy
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- On the complexity of unique solutions
- On ω-regular sets
- Relativization of questions about log space computability
- The NP-completeness column: An ongoing guide
This page was built for publication: More complicated questions about maxima and minima, and some closures of NP
