Scholars Central

Research articlePublished 30 Nov 2024

A polynomial solution for the 3-SAT problem

Authors: Geraldine Reichard

Journal of Pure and Applied Mathematics

Volume 8 · Issue 6 · Pages 01–07

Ask about this article

Abstract

Select any words in the title or abstract, or press this and choose a sentence.

In this paper, an algorithm is presented, solving the 3-SAT problem in a polynomial runtime of which implies P = NP. The 3-SAT problem is about determining, whether or not a logical expression, consisting of clauses with up to 3 literals connected by OR-expressions, that are interconnected by AND-expressions, is satisfiable. For the solution a new data structure, the 3-SAT graph, is introduced. It groups the clauses from a 3-SAT expression into coalitions, that contain all clauses with literals consisting of the same variables. The nodes of the graph represent the variables connecting the corresponding coalitions. An algorithm R will be introduced, that identifies relations between clauses by transmitting markers, called upgrades, through the graph, making use of implications. The algorithm will start sequentially for every variable and create start upgrades, one for the variables negated and one for its non-negated literals. It will be shown, that the start upgrades have to be within a specific clause pattern, called edge pattern, to mark a beginning or ending of an unsatisfiable sequence. It will be proven, that if after several execution steps of algorithm R, two corresponding start upgrades circle, then the expression is unsatisfiable and if no upgrade steps are possible anymore and the algorithm did not return unsatisfiable, the expression is satisfiable. The algorithm R is similar to already existing solutions solving 2-SAT polynomial, also making use of implications using a graph.

Ask about this article

Answers come only from this article's title, abstract and keywords, each sentence pointing to where it comes from. Your question is sent to OpenAI to write the answer. Scholars Central does not store it.

Try:

Similar by topic

More from this journal

The newest in Journal of Pure and Applied Mathematics.

All its articles

Follow

New articles from what you follow go into your email digest, once you agree to alert emails.

  • JournalJournal of Pure and Applied Mathematics
  • SubjectMathematics & Statistics
  • BylineArticles whose byline prints “Geraldine Reichard”

For authors and organisers

Publish, present and keep up with your field

Find the right journal for your paper and submit your manuscript.

Photo: Pexels