CNF Satisfiability in a Subspace and Related Problems
CNF Satisfiability in a Subspace and Related Problems
复制标题
子空间中的 CNF 可满足性及相关问题
DOI：
10.1007/s00453-022-00958-4
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Guruswami, Venkatesan
中科院分区：
文献类型：
--
作者：
Arvind, V.;Guruswami, Venkatesan
We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of polynomials overeach of which is a product of affine forms. We focus on the case ofk-CNF formulas (the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${k}-\textsc {Sub}-\textsc {Sat}$$\end{document} problem). Clearly, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${k}-\textsc {Sub}-\textsc {Sat}$$\end{document} is no easier thank-SAT, and might be harder. Indeed, via simple reductions we show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2}-\textsc {Sub}-\textsc {Sat}$$\end{document} is NP-hard, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\small \mathrm {W}}[1]$$\end{document}-hard when parameterized by the co-dimension of the subspace. We also prove that the optimization version Max-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2}-\textsc {Sub}-\textsc {Sat}$$\end{document} is NP-hard to approximate better than the trivial 3/4 ratio even on satisfiable instances. On the algorithmic front, we investigate fast exponential algorithms which give non-trivial savings over brute-force algorithms. We give a simple branching algorithm with running timefor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2}-\textsc {Sub}-\textsc {Sat}$$\end{document}, whereris the subspace dimension, as well as antime algorithm wherenis the number of variables. Turning to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${k}-\textsc {Sub}-\textsc {Sat}$$\end{document} for, while known algorithms for solving a system of degreekpolynomial equations already imply a solution with running time, we explore a more combinatorial approach. Based on an analysis of critical variables (a key notion underlying the randomizedk-SAT algorithm of Paturi, Pudlak, and Zane), we give an algorithm with running time \documentclass[12pt]{minimal} \usepackage …
We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of polynomials overeach of which is a product of affine forms. We focus on the case ofk-CNF formulas (the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${k}-\textsc {Sub}-\textsc {Sat}$$\end{document} problem). Clearly, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${k}-\textsc {Sub}-\textsc {Sat}$$\end{document} is no easier thank-SAT, and might be harder. Indeed, via simple reductions we show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2}-\textsc {Sub}-\textsc {Sat}$$\end{document} is NP-hard, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\small \mathrm {W}}[1]$$\end{document}-hard when parameterized by the co-dimension of the subspace. We also prove that the optimization version Max-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2}-\textsc {Sub}-\textsc {Sat}$$\end{document} is NP-hard to approximate better than the trivial 3/4 ratio even on satisfiable instances. On the algorithmic front, we investigate fast exponential algorithms which give non-trivial savings over brute-force algorithms. We give a simple branching algorithm with running timefor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2}-\textsc {Sub}-\textsc {Sat}$$\end{document}, whereris the subspace dimension, as well as antime algorithm wherenis the number of variables. Turning to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${k}-\textsc {Sub}-\textsc {Sat}$$\end{document} for, while known algorithms for solving a system of degreekpolynomial equations already imply a solution with running time, we explore a more combinatorial approach. Based on an analysis of critical variables (a key notion underlying the randomizedk-SAT algorithm of Paturi, Pudlak, and Zane), we give an algorithm with running time \documentclass[12pt]{minimal} \usepackage …
登录
查看更多内容
通过部分多态性约束满足问题的细粒度复杂性：一项调查
DOI：
--
发表时间：
2019
期刊：
IEEE International Symposium on Multiple-Valued Logic
影响因子：
--
作者：
Miguel Couceiro;L. Haddad;Victor Lagerkvist
通讯作者：
Victor Lagerkvist
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
Aoike Yuuki;Gima Tatsuya;Hanaka Tesshu;Kiyomi Masashi;Kobayashi Yasuaki;Kobayashi Yusuke;Kurita Kazuhiro;Otachi Yota;Suguru Tamaki
通讯作者：
Suguru Tamaki
用少于 2n 步解决可满足性问题
影响因子：
1.1
作者：
B. Monien;Ewald Speckenmeyer
通讯作者：
Ewald Speckenmeyer
强部分克隆和 SAT 问题的时间复杂度
DOI：
--
发表时间：
2017
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
P. Jonsson;Victor Lagerkvist;Gustav Nordh;B. Zanuttini
通讯作者：
B. Zanuttini
混合实例的可满足性
DOI：
--
发表时间：
2016
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
Ruiwen Chen;R. Santhanam
通讯作者：
R. Santhanam