Artificial Intelligence


On the Dual Nature of Logical Variables and Clause-Sets

Authors: Elnaserledinellah Mahmood Abdelwahab

This paper describes the conceptual approach behind the proposed solution of the 3SAT problem recently published in [Abdelwahab 2016]. It is intended for interested readers providing a step-by-step, mostly informal explanation of the new paradigm proposed there completing the picture from an epistemological point of view with the concept of duality on center-stage. After a brief introduction discussing the importance of duality in both, physics and mathematics as well as past efforts to solve the P vs. NP problem, a theorem is proven showing that true randomness of input-variables is a property of algorithms which has to be given up when discrete, finite domains are considered. This insight has an already known side effect on computation paradigms, namely: The ability to de-randomize probabilistic algorithms. The theorem uses a canonical type of de-randomization which reveals dual properties of logical variables and Clause-Sets. A distinction is made between what we call the syntactical Container Expression (CE) and the semantic Pattern Expression (PE). A single sided approach is presumed to be insufficient to solve anyone of the dual problems of efficiently finding an assignment validating a 3CNF Clause-Set and finding a 3CNF-representation for a given semantic pattern. The deeply rooted reason, hereafter referred to as The Inefficiency Principle, is conjectured to be the inherent difficulty of translating one expression into the other based on a single-sided perspective. It expresses our inability to perceive and efficiently calculate complementary properties of a logical formula applying one view only. It is proposed as an alternative to the commonly accepted P≠NP conjecture. On the other hand, the idea of algorithmically using information deduced from PE to guide the instantiation of variables in a resolution procedure applied on a CE is as per [Abdelwahab 2016] able to provide an efficient solution to the 3SAT-problem. Finally, linking de-randomization to this positive solution has various well-established and important consequences for probabilistic complexity classes which are shown to hold.

Comments: © 2016 Journal Academica Foundation. All rights reserved. With perpetual, non-exclusive license for - Originally received 08-04-2016 - accepted 09-12-2016 - published 09-15-2016 J.Acad.(N.Y.)6,3:202-239 (38 pages) - ISSN 2161-3338

Download: PDF

Submission history

[v1] 2017-09-05 04:26:06

Unique-IP document downloads: 147 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus