How to Submit
Browse
Events
Communities
About

Reducibility of 3CNF Formulas

25 September 2025, Version 1
Working Paper
This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.

Abstract

We introduce the Prime Normal Form, defined over the Prime Truth Assignments of a 3CNF formula, thus propose a procedure tackling the 3SAT problem from a different perspective. Instead of deciding if the formula is satisfiable, the procedure decides if the PNF of the formula is reducible to Canonic Truth Assignments. A CTA is a (consistent) conjunction of some PTAs, and a satisfying assignment is a conjunction of some CTAs.

Keywords

Satisfiability of Boolean Formulas
P vs NP

Comments

Comments are not moderated before they are posted, but they can be removed by the site moderators if they are found to be in contravention of our Commenting and Discussion Policy [opens in a new tab] - please read this policy before you post. Comments should be used for scholarly discussion of the content in question. You can find more information about how to use the commenting feature here [opens in a new tab] .
This site is protected by reCAPTCHA and the Google Privacy Policy [opens in a new tab] and Terms of Service [opens in a new tab] apply.

Version History

Sep 25, 2025 Version 1

Metrics

92
20
0
Views
Downloads
Citations

License

CC logo
CC
BY logo
BY
The content is available under CC BY 4.0 [opens in a new tab]

DOI

10.33774/coe-2025-l7gm7
D O I: 10.33774/coe-2025-l7gm7 [opens in a new tab]

Author’s competing interest statement

The author(s) have declared they have no conflict of interest with regard to this content

Ethics

The author(s) have declared ethics committee/IRB approval is not relevant to this content

Share