scientific article; zbMATH DE number 4001487

From MaRDI portal
Publication:4727433





Semilinear sets are subsets of \({\mathbb{N}}^ r\) (r\(\in {\mathbb{N}})\) which are finite unions of sets of the form \[ L(c;W):=\{c+\sum_{w\in W}\lambda_ w\cdot w| \quad \lambda_ w\in {\mathbb{N}}\text{ for all } w\in W\}, \] where \(c\in {\mathbb{N}}^ r\) and \(W\subset {\mathbb{N}}^ r\) is finite. The author considers the inequivalence problem (INEQ) for semilinear sets, i.e. the question whether \(L(c_ 1;W_ 1)\neq L(c_ 2;W_ 2)\) for given pairs \((c_ 1;W_ 1)\), \((c_ 2;W_ 2).\) In a previous paper he had shown that INEQ is complete for the class \(\Sigma^ p_ 2\) of the polynomial time hierarchy. Here, he gives a simplified proof for the membership \(INEQ\in \Sigma^ p_ 2\). This proof is based on the fact that, if \(L(c_ 1;W_ 1)\neq L(c_ 2;W_ 2)\), then there exists a small witness for inequality, i.e., some vector \(v\in L(c_ 1;W_ 1)\setminus L(c_ 2;W_ 2)\) whose size is bounded by some fixed polynomial of the size of the representations \((c_ 1;W_ 1)\), \((c_ 2;W_ 2)\).











This page was built for publication:

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