scientific article; zbMATH DE number 809154

zbMath0830.68064MaRDI QIDQ4852904

Mark W. Krentel, Kevin J. Rappoport, William I. Gasarch

Publication date: 28 January 1996

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP problemsOptP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

The operators min and max on the polynomial hierarchy, Complexity of counting the optimal solutions, The complexity of comparing optimal solutions, Complexity of Counting the Optimal Solutions, Most probable explanations in Bayesian networks: complexity and tractability, Counting Complexity of Minimal Cardinality and Minimal Weight Abduction, Bi-immunity results for cheatable sets, Some connections between bounded query classes and non-uniform complexity., Frequency computation and bounded queries, Deciding uniqueness in norm maximazation, The value of help bits in randomized and average-case complexity, Unnamed Item, Counting complexity of propositional abduction, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• Geometric optimization and \(D^ P\)-completeness
• The complexity of optimization problems
• The node-deletion problem for hereditary properties is NP-complete
• Optimal packing and covering in the plane are NP-complete
• Bin packing can be solved within 1+epsilon in linear time
• NP-complete scheduling problems
• Some connections between bounded query classes and non-uniform complexity.
• On the complexity of unique solutions
• The NP-Completeness of Edge-Coloring
• ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Code Generation for Expressions with Common Subexpressions
• The Complexity of Some Problems on Subsequences and Supersequences
• Complexity of Scheduling under Precedence Constraints
• The complexity of theorem-proving procedures