Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems

DOI10.1007/978-3-319-03780-6_28MaRDI QIDQ2867130zbMATH OpenOpenAlexFDO

Authors Tomoyuki Yamakami

Publication date 10 December 2013

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmlogarithmic spaceoptimization problemapproximation-preserving reduction\(\mathrm{AC}^{0}\)-circuit\(\mathrm{NC}^{1}\)-circuit

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: A significant progress has been made in the past three decades over the study of combinatorial NP optimization problems and their associated optimization and approximate classes, such as NPO, PO, APX (or APXP), and PTAS. Unfortunately, a collection of problems that are simply placed inside the P-solvable optimization class PO never have been studiously analyzed regarding their exact computational complexity. To improve this situation, the existing framework based on polynomial-time computability needs to be expanded and further refined for an insightful analysis of various approximation algorithms targeting optimization problems within PO. In particular, we deal with those problems characterized in terms of logarithmic-space computations and uniform-circuit computations. We are focused on nondeterministic logarithmic-space (NL) optimization problems or NPO problems. Our study covers a wide range of optimization and approximation classes, dubbed as, NLO, LO, APXL, and LSAS as well as new classes NC1O, APXNC1, NC1AS, and AC0O, which are founded on uniform families of Boolean circuits. Although many NL decision problems can be naturally converted into NL optimization (NLO) problems, few NLO problems have been studied vigorously. We thus provide a number of new NLO problems falling into those low-complexity classes. With the help of NC1 or AC0 approximation-preserving reductions, we also identify the most difficult problems (known as complete problems) inside those classes. Finally, we demonstrate a number of collapses and separations among those refined optimization and approximation classes with or without unproven complexity-theoretical assumptions.

Recommendations

• Fundamentals of Computation Theory
• Logspace optimization problems and their approximability properties
• Approximate solution of NP optimization problems
• Optimization, approximation, and complexity classes
• Completeness in approximation classes

Cites work

• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• A very hard log-space counting class
• Logspace optimization problems and their approximability properties
• The maximum flow problem is log space complete for P
• Undirected connectivity in log-space

Cited in

(8)

• Approximation in (poly-) logarithmic space
• Logic Programming and Nonmonotonic Reasoning
• Logical expressibility of syntactic NL for complementarity and maximization
• scientific article; zbMATH DE number 7204396 (Why is no real title available?)
• Logspace optimization problems and their approximability properties
• Fundamentals of Computation Theory
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
• Approximation in (Poly-) Logarithmic Space

This page was built for publication: Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems

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