Loading...
Please wait, while we are loading the content...
Similar Documents
The Polynomial Hierarchy collapses
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bura, Valentin |
| Copyright Year | 2019 |
| Abstract | We use Gaussian Elimination by adapting it to Exact Satisfiability. For 1-in-3 SAT instances with non-negated literals we obtain considerably smaller equivalent instances of 0/1 Integer Programming restricted to equality. Thus we obtain an upper bound for the complexity of its counting version of O(2κr2) for number of variables r and clauses-to-variables ratio κ. Combining this method with previous results gives a time and space complexity for the counting problem of O(4/3|V |2 ) and O(4/3|V |2 ). Our method shows that Positive 1-in-3 SAT may be reduced to significantly smaller instances of I.P. in the following sense: any such instance of |V | variables and |C| clauses can be polynomial-time reduced to an instance of 0/1 Integer Programming with equality only, of size at most 2/3|V | variables and at most |C| clauses. We proceed to define formally the notion of a non-trivial kernel. We define the problems considered as Constraint Satisfaction Problems. Recent advances in Computational Complexity relating to sparsification and existence of non-trivial kernels are used to conclude by showing that the method presented here, giving a non-trivial kernel for positive 1-in-3 SAT, implies the existence of a non-trivial kernel for 1-in-3 SAT. This implies the structure known as Polynomial Hierarchy collapses. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv-export-lb.library.cornell.edu/pdf/1808.02821 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
