Input domain modeling using Grobner bases and Lie-algebraic resolutions and implications for P vs NP
| Main Author: | Shrohan Mohapatra |
|---|---|
| Format: | info publication-preprint eJournal |
| Terbitan: |
, 2020
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/3996707 |
Daftar Isi:
- This article presents a novel approach to input domain modeling of some of its specific instances; those where the specifications of the function under test can be conveniently resolved into polynomial inequalities over an appropriate field. This new approach partitions the input space based on the solutions to those polynomial inequalities which can be found by computing the Grobner basis of the ideal generated by the polynomials. Another approach is a serialised version of the cellular automata that, within its own structure and granularity, partitions the input space into specific Lie-algebraic arrangement of the arguments that also satisfy the specifications. The algorithm involving Grobner bases is shown to be NP-complete and the one involving Lie-algebraic resolutions is shown to be in P. This helps one to arrive at a plausible instance that seems to be theoretically belonging to both P and NP-complete.