Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

DOI10.1007/978-3-662-44465-8_35MaRDI QIDQ2922627zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Victor Lagerkvist, Johannes Schmidt, Hannes Uppman

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.3247

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT($cdot$) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation $R$ such that SAT($R$) can be solved at least as fast as any other NP-hard SAT($cdot$) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (MaxOnes($Gamma$)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP($Delta$)). With the help of these languages we relate MaxOnes and VCSP to the exponential time hypothesis in several different ways.

Recommendations

• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Towards the Actual Relationship Between NP and Exponential Time
• Relativizations comparing NP and exponential time
• On Parameterized Exponential Time Complexity
• On parameterized exponential time complexity
• Exponential time paradigms through the polynomial time lens
• ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• New tools and connections for exponential-time approximation
• An introduction to exponential time exact algorithms for solving NP-hard problems
• Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems

Cites work

• Closure properties of constraints
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Function Algebras on Finite Sets
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Lower bounds based on the exponential time hypothesis
• On generating all solutions of generalized satisfiability problems
• On the algebraic structure of combinatorial problems
• On the complexity of k-SAT
• On the limits of sparsification
• Partial Polymorphisms and Constraint Satisfaction Problems
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• The approximability of constraint satisfaction problems
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Twice-Ramanujan sparsifiers
• Weak bases of Boolean co-clones
• Which problems have strongly exponential complexity?

Cited in

(4)

• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Precise upper and lower bounds for the monotone constraint satisfaction problem
• Towards the Actual Relationship Between NP and Exponential Time

This page was built for publication: Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922627)