[Proof Complexity] Quantum Theoretic Complexity for Satisfiability

wale oluwasanmi waleoluwasanmi at yahoo.com
Thu Mar 19 01:41:27 CET 2020

Dear Colleagues,
Based on reviews, I have a revised version of my article relating to the quantum theoretic complexity of solving the Satisfiability problem. You will find a preprint available for download here: https://engrxiv.org/8ht2m/

The same version has been submitted for conference/journal review. Here is an abstract for your referencing convenience. I do realize the topic addresses an area of high sensitivity to most computer scientists and complexity theorists and so I appreciate the time taken to consider it:
We present an algorithm, along with a correctness proof, for solving the 3 Satisfiability problem that is inspired by quantum mechanical principles and that runs in polynomial time with respect to the size of the input problem. Even though we term both our algorithm and its associated proof as quantum (for reasons which we will demonstrate), it is intended to be run on standard classical architecture. In the article, we posit that the 3 Satisfiability problem has an intrinsic complex quantum form that can be programmed in order to build a model of the solution space for satisfiable instances or show that such a model cannot be constructed. This yields surprising results on the ability for classical systems to abstractly simulate general quantum systems.

Thanks You,

More information about the Proof-Complexity mailing list