This algorithm solves NP-Complete Problems in P time

Published in

Analytics Vidhya

3 min readMar 28, 2020

The Boolean Satisfiability Problem is to write an algorithm to decide if a given boolean expression in N variables can ever take the value “true” for some choice of these N variables.

This problem is in the class NP-Complete. This means, if it were possible to write an algorithm which completes in P time, then there is a procedure to modify that algorithm to solve any other problem in the class NP in polynomial time as well.

I have just written a short javascript program which, given any boolean expression with N variables, completes in N “ticks” of the javascript clock and which makes the decision.

Since it takes N clicks of the javascript engine to run this algorithm, the efficiency is O(N), which is polynomial time.

I will explain this algorithm, make some remarks, and post the code so that its clear exactly what I am doing.

make 2 objects that holds an array, initialize one to [true], the other to [false]
each timestep, self-replicate the most recently made objects twice each, and append true, false to the array
after N timesteps, every possible set of values for the boolean variables will be in memory
if the object detects it has the correct length to do the check, then check it and update a global variable
after you check every case in a single timestep (click of the js engine) because I used self-replicating objects, terminate the program

From a practical point of view, this algorithm takes N clicks, which means it takes N steps to check all 2^N cases, where each step is “one click” of the javascript engine.

For practical concerns, any problem which can be reduced to the so-called Boolean Satisfiability Problem can now be solved by an algorithm that completes in polynomial time. I have no idea if this has any implications for pure mathematics or the P vs. NP problem, but it’s very useful for making code that runs a lot faster!

Here is the code. You can copy/paste it into a text file and save it as a .html file, open that file in your browser and type any boolean expression with variables b1, b2, … as long as you name all of your variables b + number you can write any javascript boolean expression like `b1 && b2 || b3` and click evaluate and the answer to the Boolean Satisfiability Problem will appear in the console log

<!DOCTYPE html>
<html>
<head>
 <title>Boolean satisfiability problem</title>
 <style type="text/css">
  input { width: 100%; padding: 4px; font-size: 16px; }
 </style>
</head>
<body>
 <p>Type a Boolean expression in javascript using variables b1, b2, b3, ... </p>
 <input id="expression" type="text" name="expression" />
 <button id="evaluate">Evaluate</button><script type="text/javascript">
  document.getElementById('evaluate').onclick = function() {
   var isSatisfiable = false,
    numChecked = 0,
    val = document.getElementById('expression').value,
    match = val.match(/b[0-9]*/g);
   
   if ( !match.length ) {
    console.log('no match!');
    return;
   }var totalCases = Math.pow(2, match.length);function BioObject(value) {
    if ( value.length === match.length ) {
     var params = {};
     match.forEach(function(item, idx) {
      params[item] = value[idx];
     });    with (params) {
      if ( eval(val) ) {
       isSatisfiable = true
      }      if ( ++numChecked >= totalCases ) {
        if ( isSatisfiable ) {
          console.log('is satisfiabile');
        } else {
          console.log('cannot be satisfied');
        }
      }
     }
    } else {
     setTimeout(function() {
       var t = value.slice(),
        f = value.slice();
        
       t.push(true)
       f.push(false)     new BioObject(t)
       new BioObject(f)
     }, 1)
    }
   }   new BioObject([true]);
   new BioObject([false]);
 }
 </script>
</body>
</html>

This algorithm solves NP-Complete Problems in P time

Written by calhoun137