## Abstract

We characterize the complexity of SAT instances with path-decompositions of width w (n). Although pathwidth is the most restrictive among the studied width-parameterizations of SAT, the most time-efficient algorithms known for such SAT instances run in time 2^{Ω (w (n))}, even when the path-decomposition is given in the input. We wish to better understand the decision complexity of SAT instances of width ω (log n). We provide an exact correspondence between SAT_{pw} [w (n)], the problem of SAT instances with given path decomposition of width w (n), and NL [r (n)], the class of problems decided by logspace Turing Machines with at most r (n) passes over the nondeterministic tape. In particular, we show that SAT_{pw} [w (n)] is hard for NL [frac(w (n), log n)] under log-space reductions. When NL [frac(w (n), log n)] is closed under logspace reductions, which is the case for the most interesting w (n)'s, we show that SAT_{pw} [w (n)] is also complete.

Original language | English (US) |
---|---|

Pages (from-to) | 8-12 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 110 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1 2009 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

## Keywords

- Completeness
- Computational complexity
- Fixed parameter space tractability
- Machine characterization
- Pathwidth
- SAT