Jump to content

Sat heuristic with Artificial Intelligence

fiveworlds

By fiveworlds
in Computer Science

 Share

Recommended Posts

fiveworlds

fiveworlds

Posted
Posted
Hey, I wrote an Artificial Intelligence program to solve SAT in polynomial time. It has a worst case runtime of O(2^N) and a best case runtime of O(1) for the first run of the program and an O(1) runtime thereafter.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
public class Sat {
 public static char[] getUniqueLetters(String expression){
  String letters = expression.replaceAll("(.)\\1{1,}", "$1").replace('|', ' ').replace('!',' ').replace('&',' ').replace('(',' ').replace(')',' ').replace('=',' ').replace(" ","").replace("'","");
     char[] letterarray = new char[letters.length()];
  for(int i = 0; i < letters.length(); i=i+1){
      letterarray[i]=letters.charAt(i);
  }
  return letterarray;
 };
 
 public static int[] generateIntArray(int length){
  int[] intArray = new int[length];
  for(int i = 0; i < length; i=i+1){
      intArray[i]=0;
  } return intArray;
 }
 
 public static String parse(String booleanExpression){
   while(booleanExpression.indexOf("NAND")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("NAND");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   booleanExpression = booleanExpression.replace(booleanExpression.substring(i, booleanExpression.indexOf("NAND")), "!"+booleanExpression.substring(i, booleanExpression.indexOf("NAND")));
   booleanExpression = booleanExpression.replaceFirst("NAND", "AND");
  }
  
  while(booleanExpression.indexOf("NOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("NOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   booleanExpression = booleanExpression.replace(booleanExpression.substring(i, booleanExpression.indexOf("NOR")), "!"+booleanExpression.substring(i, booleanExpression.indexOf("NOR")));
   booleanExpression = booleanExpression.replaceFirst("NOR", "OR");
  }
  
  while(booleanExpression.indexOf("XOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("XOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   countright = 0;
   countleft = 0;
   int t = booleanExpression.indexOf("XOR");
   while(t < booleanExpression.length()){
    if(booleanExpression.charAt(t)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(t)=='('){countright = countright+1;}
    t = t + 1;
    if(countleft > countright){break;}
   }
   booleanExpression = "("+booleanExpression.substring(i, t) + " && (" + booleanExpression.substring(i+1, booleanExpression.indexOf("XOR")-1) + "!="+ booleanExpression.substring(booleanExpression.indexOf("XOR")+3, t) +")";
   booleanExpression = booleanExpression.replaceFirst("XOR", "OR");
  }
  
  while(booleanExpression.indexOf("XNOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("XNOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   countright = 0;
   countleft = 0;
   int t = booleanExpression.indexOf("XNOR");
   while(t < booleanExpression.length()){
    if(booleanExpression.charAt(t)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(t)=='('){countright = countright+1;}
    t = t + 1;
    if(countleft > countright){break;}
   }
   booleanExpression = "!("+booleanExpression.substring(i, t) + " && (" + booleanExpression.substring(i+1, booleanExpression.indexOf("XNOR")-1) + "!="+ booleanExpression.substring(booleanExpression.indexOf("XNOR")+4, t) +")";
   booleanExpression = booleanExpression.replaceFirst("XNOR", "OR");
  }
  
  booleanExpression = booleanExpression.replace("OR", "||");
  booleanExpression = booleanExpression.replace("AND", "&&");
  booleanExpression = booleanExpression.replace("NOT", "!");
  return booleanExpression;
 }
 
 
 public static void main(String[] args) {
  String origbooleanExpression = "(A NAND ((((A === B) AND (A === C)) NAND (NOT(A) === C)) AND (NOT(A))))";
   try {
    File file = new File("C:/SAT/"+origbooleanExpression+".txt");
    if(file.exists() && !file.isDirectory()) {
     FileReader fileReader = new FileReader(file);
     BufferedReader bufferedReader = new BufferedReader(fileReader);
     StringBuffer stringBuffer = new StringBuffer();
     String line;
     while ((line = bufferedReader.readLine()) != null) {
      stringBuffer.append(line);
      stringBuffer.append("\n");
     }
     fileReader.close();
     System.out.println("Contents of file:");
     System.out.println(stringBuffer.toString());
     System.exit(0);
    }
   } catch (IOException e) {
    e.printStackTrace();
   
  }
  String booleanExpression = parse(origbooleanExpression);
  String output = "";
  System.out.println(booleanExpression);
  char[] letterArray = getUniqueLetters(booleanExpression);
  int[] intArray = generateIntArray(letterArray.length);
     while(intArray[intArray.length-1]<2){
      for(int i = 0; i < intArray.length-1; i=i+1){
       if(intArray[i]>1){intArray[i+1] = intArray[i+1] + 1;intArray[i]=0;}
   }
      try {
             ScriptEngineManager sem = new ScriptEngineManager();
             ScriptEngine se = sem.getEngineByName("JavaScript");
             String myExpression = booleanExpression;
             for(int i = 0; i < intArray.length; i=i+1){
              myExpression = myExpression.replace(String.valueOf(letterArray[i]), String.valueOf(Integer.toString(intArray[i]).charAt(0)));
             }
             if(se.eval(myExpression).equals(true)){
              System.out.println(myExpression);
              try{
                  PrintWriter writer = new PrintWriter("C:/SAT/"+origbooleanExpression+".txt", "UTF-8");
                  writer.println("True");
                  writer.close();
              } catch (IOException e) {
                 // do something
              }
              System.exit(0);
             }
         } catch (ScriptException e1) {
             System.out.println("Invalid Expression");
             e1.printStackTrace();
         }
      intArray[0]=intArray[0]+1;
    }
     System.out.println(output);
     try{
         PrintWriter writer = new PrintWriter("C:/SAT/"+origbooleanExpression+".txt", "UTF-8");
         writer.println("False");
         writer.close();
     } catch (IOException e) {
        // do something
     }
    }
}

 

Link to comment
Share on other sites
Strange

Strange

Posted
Posted

 

Hey, I wrote an Artificial Intelligence program to solve SAT in polynomial time. It has a worst case runtime of O(2^N) and a best case runtime of O(1) for the first run of the program and an O(1) runtime thereafter.

 

 

Can you describe the algorithm, so we don't have to reverse engineer your code.

 

Can you also show how you calculated the runtime as O(2N).

 

Also, O(2N) means exponential time, not polynomial.

 

O(N2) would be polynomial.

1
Link to comment
Share on other sites
fiveworlds

fiveworlds

Posted
  • Author
Posted (edited)

I have improved the heuristic to run in O(1) time :) Basically it required a big demultiplexer that we can't really make because it is too dificult but we can make a computer generate the demultiplexer for us.

 

 

package x;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
public class Sat {
 public static String
  ORINGINAL_BOOLEAN_EXPRESSION = "((A   AND NOT A) AND (A))",
  FILE_LOCATION = "C:/SAT/"+ORINGINAL_BOOLEAN_EXPRESSION+".txt",
  FILE_ENCODING = "UTF-8",
  SCRIPTING_ENGINE = "Javascript";
 
 /*
  * write the file
  *
  */
 public static void writeFile(String Result){
  try{
         PrintWriter writer = new PrintWriter(FILE_LOCATION, FILE_ENCODING);
         writer.println(Result);
         writer.close();
         System.exit(0);
     } catch (IOException e) {
        // do something
     }
 }
 
 /*
  * parse out anything that isn't a letter
  *
  */
 public static char[] getUniqueLetters(String expression){
  String letters = expression.replaceAll("(.)\\1{1,}", "$1").replace('|', ' ').replace('!',' ').replace('&',' ').replace('(',' ').replace(')',' ').replace('=',' ').replace(" ","").replace("'","");
     char[] letterarray = new char[letters.length()];
  for(int i = 0; i < letters.length(); i=i+1){
      letterarray[i]=letters.charAt(i);
  }
  return letterarray;
 };
 
 public static int[] generateIntArray(int length){
  int[] intArray = new int[length];
  for(int i = 0; i < length; i=i+1){
      intArray[i]=0;
  } return intArray;
 }
 
 public static String parse(String booleanExpression){
  
   while(booleanExpression.indexOf("NAND")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("NAND");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   booleanExpression = booleanExpression.replace(booleanExpression.substring(i, booleanExpression.indexOf("NAND")), "!"+booleanExpression.substring(i, booleanExpression.indexOf("NAND")));
   booleanExpression = booleanExpression.replaceFirst("NAND", "AND");
  }
  
  while(booleanExpression.indexOf("NOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("NOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   booleanExpression = booleanExpression.replace(booleanExpression.substring(i, booleanExpression.indexOf("NOR")), "!"+booleanExpression.substring(i, booleanExpression.indexOf("NOR")));
   booleanExpression = booleanExpression.replaceFirst("NOR", "OR");
  }
  
  while(booleanExpression.indexOf("XOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("XOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   countright = 0;
   countleft = 0;
   int t = booleanExpression.indexOf("XOR");
   while(t < booleanExpression.length()){
    if(booleanExpression.charAt(t)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(t)=='('){countright = countright+1;}
    t = t + 1;
    if(countleft > countright){break;}
   }
   booleanExpression = "("+booleanExpression.substring(i, t) + " && (" + booleanExpression.substring(i+1, booleanExpression.indexOf("XOR")-1) + "!="+ booleanExpression.substring(booleanExpression.indexOf("XOR")+3, t) +")";
   booleanExpression = booleanExpression.replaceFirst("XOR", "OR");
  }
  
  while(booleanExpression.indexOf("XNOR")!=-1){
   int countright = 0;
   int countleft = 0;
   int i = booleanExpression.indexOf("XNOR");
   while(i > -1){
    if(booleanExpression.charAt(i)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(i)=='('){countright = countright+1;}
    if(countright > countleft){break;}    
    i = i - 1;
   }
   countright = 0;
   countleft = 0;
   int t = booleanExpression.indexOf("XNOR");
   while(t < booleanExpression.length()){
    if(booleanExpression.charAt(t)==')'){countleft = countleft + 1;}
    if(booleanExpression.charAt(t)=='('){countright = countright+1;}
    t = t + 1;
    if(countleft > countright){break;}
   }
   booleanExpression = "!("+booleanExpression.substring(i, t) + " && (" + booleanExpression.substring(i+1, booleanExpression.indexOf("XNOR")-1) + "!="+ booleanExpression.substring(booleanExpression.indexOf("XNOR")+4, t) +")";
   booleanExpression = booleanExpression.replaceFirst("XNOR", "OR");
  }
  
  booleanExpression = booleanExpression.replace("OR", "||");
  booleanExpression = booleanExpression.replace("AND", "&&");
  booleanExpression = booleanExpression.replace("NOT", "!");
  return booleanExpression;
 }
 
 public static void noDuplication(String booleanExpression,char[] letterArray){
  int count = 1;
  for(int i = 0; i < letterArray.length; i ++){
   int temp = booleanExpression.length() - booleanExpression.replace(String.valueOf(letterArray[i]),"").length();
   if(temp>count){
    count = temp;
   }
  }
  if(count == 1){
   System.out.println("No Duplicates");
   writeFile("True");
   System.exit(0);
  }
 }
 
 public static void main(String[] args) {
  
   try {
    File file = new File("C:/SAT/"+ORINGINAL_BOOLEAN_EXPRESSION+".txt");
    if(file.exists() && !file.isDirectory()) {
     FileReader fileReader = new FileReader(file);
     BufferedReader bufferedReader = new BufferedReader(fileReader);
     StringBuffer stringBuffer = new StringBuffer();
     String line;
     while ((line = bufferedReader.readLine()) != null) {
      stringBuffer.append(line);
      stringBuffer.append("\n");
     }
     fileReader.close();
     System.out.println("Contents of file:");
     System.out.println(stringBuffer.toString());
     System.exit(0);
    }
   } catch (IOException e) {
    e.printStackTrace();
   
  }
  String booleanExpression = parse(ORINGINAL_BOOLEAN_EXPRESSION);
  while(booleanExpression.indexOf("  ")!=-1){
   booleanExpression = booleanExpression.replace("  ", " ");
  }
  
  String output = "";
  System.out.println(booleanExpression);
  char[] letterArray = getUniqueLetters(booleanExpression);
  
  noDuplication(booleanExpression,letterArray);
  
  while(booleanExpression.indexOf("! ")!=-1){
   booleanExpression = booleanExpression.replace("! ", "!");
  }
  boolean match = true;
  while (match == true){
   match=false;
   for(int i = 0; i < letterArray.length; i ++){   
    while(booleanExpression.indexOf("!("+letterArray[i]+"&&"+ "!" +letterArray[i])!=-1){
     booleanExpression = booleanExpression.replace(String.valueOf(letterArray[i])+"&&"+String.valueOf(letterArray[i]),"(true");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(!"+letterArray[i]+"&&" +letterArray[i])!=-1){
     booleanExpression = booleanExpression.replace(String.valueOf(letterArray[i])+"&&"+String.valueOf(letterArray[i]),"(true");
     match=true;
    }
    
    while(booleanExpression.indexOf("("+letterArray[i]+" &&"+ " !" +letterArray[i]+")")!=-1){
     booleanExpression = booleanExpression.replace("("+letterArray[i]+" &&"+ " !" +letterArray[i]+")","false");
     match=true;
    }
  
    while(booleanExpression.indexOf("(!"+letterArray[i]+" &&"+ " " +letterArray[i]+")")!=-1){
     booleanExpression = booleanExpression.replace("(!"+letterArray[i]+" &&"+ " " +letterArray[i]+")","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("(false && (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("(false && (" +letterArray[i]+"))","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("((" +letterArray[i]+") && false)")!=-1) {
     booleanExpression = booleanExpression.replace("((" +letterArray[i]+") && false)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("(true && (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("(true && (" +letterArray[i]+"))","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("((" +letterArray[i]+") && true)")!=-1) {
     booleanExpression = booleanExpression.replace("((" +letterArray[i]+") && true)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(false && (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("!(false && (" +letterArray[i]+"))","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!((" +letterArray[i]+") && false)")!=-1) {
     booleanExpression = booleanExpression.replace("!((" +letterArray[i]+") && false)","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(true && (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("!(true && (" +letterArray[i]+"))","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!((" +letterArray[i]+") && true)")!=-1) {
     booleanExpression = booleanExpression.replace("!((" +letterArray[i]+") && true)","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!((" +letterArray[i]+") || true)")!=-1) {
     booleanExpression = booleanExpression.replace("!((" +letterArray[i]+") || true)","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(true || (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("!(true || (" +letterArray[i]+"))","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!((" +letterArray[i]+") || false)")!=-1) {
     booleanExpression = booleanExpression.replace("!((" +letterArray[i]+") || false)","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(false || (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("!(false || (" +letterArray[i]+"))","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("((" +letterArray[i]+") || true)")!=-1) {
     booleanExpression = booleanExpression.replace("((" +letterArray[i]+") || true)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("(true || (" +letterArray[i]+"))")!=-1) {
     booleanExpression = booleanExpression.replace("(true || (" +letterArray[i]+"))","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(true || true)")!=-1) {
     booleanExpression = booleanExpression.replace("!(true || true)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(true || false)")!=-1) {
     booleanExpression = booleanExpression.replace("!(true || false)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(false || true)")!=-1) {
     booleanExpression = booleanExpression.replace("!((" +letterArray[i]+") && true)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("!(false || false)")!=-1) {
     booleanExpression = booleanExpression.replace("!(false || false)","false");
     match=true;
    }
    
    while(booleanExpression.indexOf("(true || true)")!=-1) {
     booleanExpression = booleanExpression.replace("(true || true)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("(true || false)")!=-1) {
     booleanExpression = booleanExpression.replace("(true || false)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("(false || true)")!=-1) {
     booleanExpression = booleanExpression.replace("(false || true)","true");
     match=true;
    }
    
    while(booleanExpression.indexOf("(false || false)")!=-1) {
     booleanExpression = booleanExpression.replace("(false || false)","false");
     match=true;
    }
    
    if(booleanExpression.indexOf("||")!=-1){
     int countright = 0;
     int countleft = 0;
     int i1 = 1;
     while(i1 < booleanExpression.length()){
      if(booleanExpression.charAt(i1)==')'){countleft = countleft + 1;}
      if(booleanExpression.charAt(i1)=='('){countright = countright+1;}
      if((booleanExpression.charAt(i1)=='|') && (countright == countleft)){
       noDuplication(booleanExpression.substring(0, i1),letterArray);
       noDuplication(booleanExpression.substring(i1, booleanExpression.length()).substring(0, i1),letterArray);
       break;
      }    
      i1 = i1 + 1;
     }
    }
   }
  }
  System.out.println(booleanExpression);
  if(booleanExpression.equals("true")){
   writeFile("True");
  }
  
  if(booleanExpression.equals("false")){
   try{
          PrintWriter writer = new PrintWriter(FILE_LOCATION, FILE_ENCODING);
          writer.println("False");
          writer.close();
      } catch (IOException e) {
         // do something
      }
   
   System.exit(0);
  }
  
  
  if((booleanExpression.length() - booleanExpression.replace(String.valueOf("||"),"").length() / 2) == letterArray.length){writeFile("True");};
  
  
  System.out.println("loop");
  String letters = "";
  for(int i = 0; i < letterArray.length; i++){
   if(booleanExpression.indexOf(letterArray[i])!=-1){
    letters = letters + letterArray[i];
   }
  }
  char[] lettersArray2= new char[letters.length()];
  if(letters.length()>0){
   lettersArray2 = new char[letters.length()];
   for(int i = 0; i < letters.length(); i++){
    lettersArray2[i] = letters.charAt(i);
   }
  } else {
         PrintWriter writer;
   try {
    writer = new PrintWriter(FILE_LOCATION, FILE_ENCODING);
    writer.println(Boolean.parseBoolean(booleanExpression));
             writer.close();
   } catch (FileNotFoundException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   } catch (UnsupportedEncodingException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   System.exit(0);
  }
  
  int[] intArray = generateIntArray(lettersArray2.length);
     while(intArray[intArray.length-1]<2){
      for(int i = 0; i < intArray.length-1; i=i+1){
       if(intArray[i]>1){intArray[i+1] = intArray[i+1] + 1;intArray[i]=0;}
   }
      try {
             ScriptEngineManager sem = new ScriptEngineManager();
             ScriptEngine se = sem.getEngineByName("Javascript");
             String myExpression = booleanExpression;
             for(int i = 0; i < intArray.length; i=i+1){
              myExpression = myExpression.replace(String.valueOf(lettersArray2[i]), String.valueOf(Integer.toString(intArray[i]).charAt(0)));
             }
             System.out.println(myExpression);
             if(se.eval(myExpression).equals(true)){
              System.out.println(myExpression);
              writeFile("True");
             }
         } catch (ScriptException e1) {
             System.out.println("Invalid Expression");
             e1.printStackTrace();
         }
      intArray[0]=intArray[0]+1;
    }
     System.out.println(output);
     try{
         PrintWriter writer = new PrintWriter(FILE_LOCATION, FILE_ENCODING);
         writer.println("False");
         writer.close();
     } catch (IOException e) {
        // do something
     }
    }
}
Edited by fiveworlds
Link to comment
Share on other sites
Strange

Strange

Posted
Posted

Ahem.

 

 

 

Can you describe the algorithm, so we don't have to reverse engineer your code.

 

Can you also show how you calculated the runtime as O(2N).

 

Also, O(2N) means exponential time, not polynomial.

 

O(N2) would be polynomial.

Link to comment
Share on other sites
EdEarl

EdEarl

Posted
Posted (edited)

Can you describe the algorithm, so we don't have to reverse engineer your code.

 

Can you also show how you calculated the runtime as O(2N).

 

Also, O(2N) means exponential time, not polynomial.

 

O(N2) would be polynomial.

Yes, need all of the above. Additionally, inputs and outputs might be valuable. What is Sat?

Edited by EdEarl
Link to comment
Share on other sites
John Cuthber

John Cuthber

Posted
Posted

I have improved the heuristic to run in O(1) time :) Basically it required a big demultiplexer that we can't really make because it is too dificult but we can make a computer generate the demultiplexer for us.

How long does it take for the computer to create it?

Is it,as I suspect, O(2^N)

 

And, as several people have asked already

What do you think "SAT" means?

1
Link to comment
Share on other sites
John Cuthber

John Cuthber

Posted
Posted

I have an algorithm that answers the travelling salesman problem in O(n)

1 Get the data for the locations to visit

2 get the computer to do the calculation

3 print the locations in order of visiting.

 

OK step 2 needs work...

:)

Link to comment
Share on other sites
fiveworlds

fiveworlds

Posted
  • Author
Posted (edited)

We can actually generate the O(1) equation for the above now it is.

var booleanExpression = "(((a AND a) AND !(a AND a)) AND ((a AND a) AND !(a AND a)))";
for(var i = 0; i < 4; i = i +1){
booleanExpression = booleanExpression.replace('(a AND !a)','false').replace('(a AND a)','true').replace('(a AND b)','true').replace('(a AND c)','true').replace('(a AND d)','true').replace('(a AND e)','true').replace('(a AND f)','true').replace('(a AND g)','true').replace('(a AND i)','true').replace('(a AND h)','true').replace('(a AND j)','true').replace('(a AND k)','true').replace('(a AND l)','true').replace('(a AND m)','true').replace('(a AND n)','true').replace('(a AND o)','true').replace('(a AND p)','true').replace('(a AND q)','true').replace('(a AND r)','true').replace('(a AND s)','true').replace('(a AND t)','true').replace('(a AND u)','true').replace('(a AND v)','true').replace('(a AND w)','true').replace('(a AND x)','true').replace('(a AND y)','true').replace('(a AND z)','true').replace('(!a AND a)','false').replace('(a AND !a)','true').replace('(!a AND !a)','true').replace('!(a AND !a)','true').replace('!(!a AND !a)','true').replace('!(a AND !a)','true').replace('!(!a AND !a)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(b AND !b)','false').replace('(b AND a)','true').replace('(b AND b)','true').replace('(b AND c)','true').replace('(b AND d)','true').replace('(b AND e)','true').replace('(b AND f)','true').replace('(b AND g)','true').replace('(b AND i)','true').replace('(b AND h)','true').replace('(b AND j)','true').replace('(b AND k)','true').replace('(b AND l)','true').replace('(b AND m)','true').replace('(b AND n)','true').replace('(b AND o)','true').replace('(b AND p)','true').replace('(b AND q)','true').replace('(b AND r)','true').replace('(b AND s)','true').replace('(b AND t)','true').replace('(b AND u)','true').replace('(b AND v)','true').replace('(b AND w)','true').replace('(b AND x)','true').replace('(b AND y)','true').replace('(b AND z)','true').replace('(!b AND b)','false').replace('(b AND !b)','true').replace('(!b AND !b)','true').replace('!(b AND !b)','true').replace('!(!b AND !b)','true').replace('!(b AND !b)','true').replace('!(!b AND !b)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(c AND !c)','false').replace('(c AND a)','true').replace('(c AND b)','true').replace('(c AND c)','true').replace('(c AND d)','true').replace('(c AND e)','true').replace('(c AND f)','true').replace('(c AND g)','true').replace('(c AND i)','true').replace('(c AND h)','true').replace('(c AND j)','true').replace('(c AND k)','true').replace('(c AND l)','true').replace('(c AND m)','true').replace('(c AND n)','true').replace('(c AND o)','true').replace('(c AND p)','true').replace('(c AND q)','true').replace('(c AND r)','true').replace('(c AND s)','true').replace('(c AND t)','true').replace('(c AND u)','true').replace('(c AND v)','true').replace('(c AND w)','true').replace('(c AND x)','true').replace('(c AND y)','true').replace('(c AND z)','true').replace('(!c AND c)','false').replace('(c AND !c)','true').replace('(!c AND !c)','true').replace('!(c AND !c)','true').replace('!(!c AND !c)','true').replace('!(c AND !c)','true').replace('!(!c AND !c)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(d AND !d)','false').replace('(d AND a)','true').replace('(d AND b)','true').replace('(d AND c)','true').replace('(d AND d)','true').replace('(d AND e)','true').replace('(d AND f)','true').replace('(d AND g)','true').replace('(d AND i)','true').replace('(d AND h)','true').replace('(d AND j)','true').replace('(d AND k)','true').replace('(d AND l)','true').replace('(d AND m)','true').replace('(d AND n)','true').replace('(d AND o)','true').replace('(d AND p)','true').replace('(d AND q)','true').replace('(d AND r)','true').replace('(d AND s)','true').replace('(d AND t)','true').replace('(d AND u)','true').replace('(d AND v)','true').replace('(d AND w)','true').replace('(d AND x)','true').replace('(d AND y)','true').replace('(d AND z)','true').replace('(!d AND d)','false').replace('(d AND !d)','true').replace('(!d AND !d)','true').replace('!(d AND !d)','true').replace('!(!d AND !d)','true').replace('!(d AND !d)','true').replace('!(!d AND !d)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(e AND !e)','false').replace('(e AND a)','true').replace('(e AND b)','true').replace('(e AND c)','true').replace('(e AND d)','true').replace('(e AND e)','true').replace('(e AND f)','true').replace('(e AND g)','true').replace('(e AND i)','true').replace('(e AND h)','true').replace('(e AND j)','true').replace('(e AND k)','true').replace('(e AND l)','true').replace('(e AND m)','true').replace('(e AND n)','true').replace('(e AND o)','true').replace('(e AND p)','true').replace('(e AND q)','true').replace('(e AND r)','true').replace('(e AND s)','true').replace('(e AND t)','true').replace('(e AND u)','true').replace('(e AND v)','true').replace('(e AND w)','true').replace('(e AND x)','true').replace('(e AND y)','true').replace('(e AND z)','true').replace('(!e AND e)','false').replace('(e AND !e)','true').replace('(!e AND !e)','true').replace('!(e AND !e)','true').replace('!(!e AND !e)','true').replace('!(e AND !e)','true').replace('!(!e AND !e)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(f AND !f)','false').replace('(f AND a)','true').replace('(f AND b)','true').replace('(f AND c)','true').replace('(f AND d)','true').replace('(f AND e)','true').replace('(f AND f)','true').replace('(f AND g)','true').replace('(f AND i)','true').replace('(f AND h)','true').replace('(f AND j)','true').replace('(f AND k)','true').replace('(f AND l)','true').replace('(f AND m)','true').replace('(f AND n)','true').replace('(f AND o)','true').replace('(f AND p)','true').replace('(f AND q)','true').replace('(f AND r)','true').replace('(f AND s)','true').replace('(f AND t)','true').replace('(f AND u)','true').replace('(f AND v)','true').replace('(f AND w)','true').replace('(f AND x)','true').replace('(f AND y)','true').replace('(f AND z)','true').replace('(!f AND f)','false').replace('(f AND !f)','true').replace('(!f AND !f)','true').replace('!(f AND !f)','true').replace('!(!f AND !f)','true').replace('!(f AND !f)','true').replace('!(!f AND !f)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(g AND !g)','false').replace('(g AND a)','true').replace('(g AND b)','true').replace('(g AND c)','true').replace('(g AND d)','true').replace('(g AND e)','true').replace('(g AND f)','true').replace('(g AND g)','true').replace('(g AND i)','true').replace('(g AND h)','true').replace('(g AND j)','true').replace('(g AND k)','true').replace('(g AND l)','true').replace('(g AND m)','true').replace('(g AND n)','true').replace('(g AND o)','true').replace('(g AND p)','true').replace('(g AND q)','true').replace('(g AND r)','true').replace('(g AND s)','true').replace('(g AND t)','true').replace('(g AND u)','true').replace('(g AND v)','true').replace('(g AND w)','true').replace('(g AND x)','true').replace('(g AND y)','true').replace('(g AND z)','true').replace('(!g AND g)','false').replace('(g AND !g)','true').replace('(!g AND !g)','true').replace('!(g AND !g)','true').replace('!(!g AND !g)','true').replace('!(g AND !g)','true').replace('!(!g AND !g)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(i AND !i)','false').replace('(i AND a)','true').replace('(i AND b)','true').replace('(i AND c)','true').replace('(i AND d)','true').replace('(i AND e)','true').replace('(i AND f)','true').replace('(i AND g)','true').replace('(i AND i)','true').replace('(i AND h)','true').replace('(i AND j)','true').replace('(i AND k)','true').replace('(i AND l)','true').replace('(i AND m)','true').replace('(i AND n)','true').replace('(i AND o)','true').replace('(i AND p)','true').replace('(i AND q)','true').replace('(i AND r)','true').replace('(i AND s)','true').replace('(i AND t)','true').replace('(i AND u)','true').replace('(i AND v)','true').replace('(i AND w)','true').replace('(i AND x)','true').replace('(i AND y)','true').replace('(i AND z)','true').replace('(!i AND i)','false').replace('(i AND !i)','true').replace('(!i AND !i)','true').replace('!(i AND !i)','true').replace('!(!i AND !i)','true').replace('!(i AND !i)','true').replace('!(!i AND !i)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(h AND !h)','false').replace('(h AND a)','true').replace('(h AND b)','true').replace('(h AND c)','true').replace('(h AND d)','true').replace('(h AND e)','true').replace('(h AND f)','true').replace('(h AND g)','true').replace('(h AND i)','true').replace('(h AND h)','true').replace('(h AND j)','true').replace('(h AND k)','true').replace('(h AND l)','true').replace('(h AND m)','true').replace('(h AND n)','true').replace('(h AND o)','true').replace('(h AND p)','true').replace('(h AND q)','true').replace('(h AND r)','true').replace('(h AND s)','true').replace('(h AND t)','true').replace('(h AND u)','true').replace('(h AND v)','true').replace('(h AND w)','true').replace('(h AND x)','true').replace('(h AND y)','true').replace('(h AND z)','true').replace('(!h AND h)','false').replace('(h AND !h)','true').replace('(!h AND !h)','true').replace('!(h AND !h)','true').replace('!(!h AND !h)','true').replace('!(h AND !h)','true').replace('!(!h AND !h)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(j AND !j)','false').replace('(j AND a)','true').replace('(j AND b)','true').replace('(j AND c)','true').replace('(j AND d)','true').replace('(j AND e)','true').replace('(j AND f)','true').replace('(j AND g)','true').replace('(j AND i)','true').replace('(j AND h)','true').replace('(j AND j)','true').replace('(j AND k)','true').replace('(j AND l)','true').replace('(j AND m)','true').replace('(j AND n)','true').replace('(j AND o)','true').replace('(j AND p)','true').replace('(j AND q)','true').replace('(j AND r)','true').replace('(j AND s)','true').replace('(j AND t)','true').replace('(j AND u)','true').replace('(j AND v)','true').replace('(j AND w)','true').replace('(j AND x)','true').replace('(j AND y)','true').replace('(j AND z)','true').replace('(!j AND j)','false').replace('(j AND !j)','true').replace('(!j AND !j)','true').replace('!(j AND !j)','true').replace('!(!j AND !j)','true').replace('!(j AND !j)','true').replace('!(!j AND !j)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(k AND !k)','false').replace('(k AND a)','true').replace('(k AND b)','true').replace('(k AND c)','true').replace('(k AND d)','true').replace('(k AND e)','true').replace('(k AND f)','true').replace('(k AND g)','true').replace('(k AND i)','true').replace('(k AND h)','true').replace('(k AND j)','true').replace('(k AND k)','true').replace('(k AND l)','true').replace('(k AND m)','true').replace('(k AND n)','true').replace('(k AND o)','true').replace('(k AND p)','true').replace('(k AND q)','true').replace('(k AND r)','true').replace('(k AND s)','true').replace('(k AND t)','true').replace('(k AND u)','true').replace('(k AND v)','true').replace('(k AND w)','true').replace('(k AND x)','true').replace('(k AND y)','true').replace('(k AND z)','true').replace('(!k AND k)','false').replace('(k AND !k)','true').replace('(!k AND !k)','true').replace('!(k AND !k)','true').replace('!(!k AND !k)','true').replace('!(k AND !k)','true').replace('!(!k AND !k)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(l AND !l)','false').replace('(l AND a)','true').replace('(l AND b)','true').replace('(l AND c)','true').replace('(l AND d)','true').replace('(l AND e)','true').replace('(l AND f)','true').replace('(l AND g)','true').replace('(l AND i)','true').replace('(l AND h)','true').replace('(l AND j)','true').replace('(l AND k)','true').replace('(l AND l)','true').replace('(l AND m)','true').replace('(l AND n)','true').replace('(l AND o)','true').replace('(l AND p)','true').replace('(l AND q)','true').replace('(l AND r)','true').replace('(l AND s)','true').replace('(l AND t)','true').replace('(l AND u)','true').replace('(l AND v)','true').replace('(l AND w)','true').replace('(l AND x)','true').replace('(l AND y)','true').replace('(l AND z)','true').replace('(!l AND l)','false').replace('(l AND !l)','true').replace('(!l AND !l)','true').replace('!(l AND !l)','true').replace('!(!l AND !l)','true').replace('!(l AND !l)','true').replace('!(!l AND !l)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(m AND !m)','false').replace('(m AND a)','true').replace('(m AND b)','true').replace('(m AND c)','true').replace('(m AND d)','true').replace('(m AND e)','true').replace('(m AND f)','true').replace('(m AND g)','true').replace('(m AND i)','true').replace('(m AND h)','true').replace('(m AND j)','true').replace('(m AND k)','true').replace('(m AND l)','true').replace('(m AND m)','true').replace('(m AND n)','true').replace('(m AND o)','true').replace('(m AND p)','true').replace('(m AND q)','true').replace('(m AND r)','true').replace('(m AND s)','true').replace('(m AND t)','true').replace('(m AND u)','true').replace('(m AND v)','true').replace('(m AND w)','true').replace('(m AND x)','true').replace('(m AND y)','true').replace('(m AND z)','true').replace('(!m AND m)','false').replace('(m AND !m)','true').replace('(!m AND !m)','true').replace('!(m AND !m)','true').replace('!(!m AND !m)','true').replace('!(m AND !m)','true').replace('!(!m AND !m)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(n AND !n)','false').replace('(n AND a)','true').replace('(n AND b)','true').replace('(n AND c)','true').replace('(n AND d)','true').replace('(n AND e)','true').replace('(n AND f)','true').replace('(n AND g)','true').replace('(n AND i)','true').replace('(n AND h)','true').replace('(n AND j)','true').replace('(n AND k)','true').replace('(n AND l)','true').replace('(n AND m)','true').replace('(n AND n)','true').replace('(n AND o)','true').replace('(n AND p)','true').replace('(n AND q)','true').replace('(n AND r)','true').replace('(n AND s)','true').replace('(n AND t)','true').replace('(n AND u)','true').replace('(n AND v)','true').replace('(n AND w)','true').replace('(n AND x)','true').replace('(n AND y)','true').replace('(n AND z)','true').replace('(!n AND n)','false').replace('(n AND !n)','true').replace('(!n AND !n)','true').replace('!(n AND !n)','true').replace('!(!n AND !n)','true').replace('!(n AND !n)','true').replace('!(!n AND !n)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(o AND !o)','false').replace('(o AND a)','true').replace('(o AND b)','true').replace('(o AND c)','true').replace('(o AND d)','true').replace('(o AND e)','true').replace('(o AND f)','true').replace('(o AND g)','true').replace('(o AND i)','true').replace('(o AND h)','true').replace('(o AND j)','true').replace('(o AND k)','true').replace('(o AND l)','true').replace('(o AND m)','true').replace('(o AND n)','true').replace('(o AND o)','true').replace('(o AND p)','true').replace('(o AND q)','true').replace('(o AND r)','true').replace('(o AND s)','true').replace('(o AND t)','true').replace('(o AND u)','true').replace('(o AND v)','true').replace('(o AND w)','true').replace('(o AND x)','true').replace('(o AND y)','true').replace('(o AND z)','true').replace('(!o AND o)','false').replace('(o AND !o)','true').replace('(!o AND !o)','true').replace('!(o AND !o)','true').replace('!(!o AND !o)','true').replace('!(o AND !o)','true').replace('!(!o AND !o)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(p AND !p)','false').replace('(p AND a)','true').replace('(p AND b)','true').replace('(p AND c)','true').replace('(p AND d)','true').replace('(p AND e)','true').replace('(p AND f)','true').replace('(p AND g)','true').replace('(p AND i)','true').replace('(p AND h)','true').replace('(p AND j)','true').replace('(p AND k)','true').replace('(p AND l)','true').replace('(p AND m)','true').replace('(p AND n)','true').replace('(p AND o)','true').replace('(p AND p)','true').replace('(p AND q)','true').replace('(p AND r)','true').replace('(p AND s)','true').replace('(p AND t)','true').replace('(p AND u)','true').replace('(p AND v)','true').replace('(p AND w)','true').replace('(p AND x)','true').replace('(p AND y)','true').replace('(p AND z)','true').replace('(!p AND p)','false').replace('(p AND !p)','true').replace('(!p AND !p)','true').replace('!(p AND !p)','true').replace('!(!p AND !p)','true').replace('!(p AND !p)','true').replace('!(!p AND !p)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(q AND !q)','false').replace('(q AND a)','true').replace('(q AND b)','true').replace('(q AND c)','true').replace('(q AND d)','true').replace('(q AND e)','true').replace('(q AND f)','true').replace('(q AND g)','true').replace('(q AND i)','true').replace('(q AND h)','true').replace('(q AND j)','true').replace('(q AND k)','true').replace('(q AND l)','true').replace('(q AND m)','true').replace('(q AND n)','true').replace('(q AND o)','true').replace('(q AND p)','true').replace('(q AND q)','true').replace('(q AND r)','true').replace('(q AND s)','true').replace('(q AND t)','true').replace('(q AND u)','true').replace('(q AND v)','true').replace('(q AND w)','true').replace('(q AND x)','true').replace('(q AND y)','true').replace('(q AND z)','true').replace('(!q AND q)','false').replace('(q AND !q)','true').replace('(!q AND !q)','true').replace('!(q AND !q)','true').replace('!(!q AND !q)','true').replace('!(q AND !q)','true').replace('!(!q AND !q)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(r AND !r)','false').replace('(r AND a)','true').replace('(r AND b)','true').replace('(r AND c)','true').replace('(r AND d)','true').replace('(r AND e)','true').replace('(r AND f)','true').replace('(r AND g)','true').replace('(r AND i)','true').replace('(r AND h)','true').replace('(r AND j)','true').replace('(r AND k)','true').replace('(r AND l)','true').replace('(r AND m)','true').replace('(r AND n)','true').replace('(r AND o)','true').replace('(r AND p)','true').replace('(r AND q)','true').replace('(r AND r)','true').replace('(r AND s)','true').replace('(r AND t)','true').replace('(r AND u)','true').replace('(r AND v)','true').replace('(r AND w)','true').replace('(r AND x)','true').replace('(r AND y)','true').replace('(r AND z)','true').replace('(!r AND r)','false').replace('(r AND !r)','true').replace('(!r AND !r)','true').replace('!(r AND !r)','true').replace('!(!r AND !r)','true').replace('!(r AND !r)','true').replace('!(!r AND !r)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(s AND !s)','false').replace('(s AND a)','true').replace('(s AND b)','true').replace('(s AND c)','true').replace('(s AND d)','true').replace('(s AND e)','true').replace('(s AND f)','true').replace('(s AND g)','true').replace('(s AND i)','true').replace('(s AND h)','true').replace('(s AND j)','true').replace('(s AND k)','true').replace('(s AND l)','true').replace('(s AND m)','true').replace('(s AND n)','true').replace('(s AND o)','true').replace('(s AND p)','true').replace('(s AND q)','true').replace('(s AND r)','true').replace('(s AND s)','true').replace('(s AND t)','true').replace('(s AND u)','true').replace('(s AND v)','true').replace('(s AND w)','true').replace('(s AND x)','true').replace('(s AND y)','true').replace('(s AND z)','true').replace('(!s AND s)','false').replace('(s AND !s)','true').replace('(!s AND !s)','true').replace('!(s AND !s)','true').replace('!(!s AND !s)','true').replace('!(s AND !s)','true').replace('!(!s AND !s)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(t AND !t)','false').replace('(t AND a)','true').replace('(t AND b)','true').replace('(t AND c)','true').replace('(t AND d)','true').replace('(t AND e)','true').replace('(t AND f)','true').replace('(t AND g)','true').replace('(t AND i)','true').replace('(t AND h)','true').replace('(t AND j)','true').replace('(t AND k)','true').replace('(t AND l)','true').replace('(t AND m)','true').replace('(t AND n)','true').replace('(t AND o)','true').replace('(t AND p)','true').replace('(t AND q)','true').replace('(t AND r)','true').replace('(t AND s)','true').replace('(t AND t)','true').replace('(t AND u)','true').replace('(t AND v)','true').replace('(t AND w)','true').replace('(t AND x)','true').replace('(t AND y)','true').replace('(t AND z)','true').replace('(!t AND t)','false').replace('(t AND !t)','true').replace('(!t AND !t)','true').replace('!(t AND !t)','true').replace('!(!t AND !t)','true').replace('!(t AND !t)','true').replace('!(!t AND !t)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(u AND !u)','false').replace('(u AND a)','true').replace('(u AND b)','true').replace('(u AND c)','true').replace('(u AND d)','true').replace('(u AND e)','true').replace('(u AND f)','true').replace('(u AND g)','true').replace('(u AND i)','true').replace('(u AND h)','true').replace('(u AND j)','true').replace('(u AND k)','true').replace('(u AND l)','true').replace('(u AND m)','true').replace('(u AND n)','true').replace('(u AND o)','true').replace('(u AND p)','true').replace('(u AND q)','true').replace('(u AND r)','true').replace('(u AND s)','true').replace('(u AND t)','true').replace('(u AND u)','true').replace('(u AND v)','true').replace('(u AND w)','true').replace('(u AND x)','true').replace('(u AND y)','true').replace('(u AND z)','true').replace('(!u AND u)','false').replace('(u AND !u)','true').replace('(!u AND !u)','true').replace('!(u AND !u)','true').replace('!(!u AND !u)','true').replace('!(u AND !u)','true').replace('!(!u AND !u)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(v AND !v)','false').replace('(v AND a)','true').replace('(v AND b)','true').replace('(v AND c)','true').replace('(v AND d)','true').replace('(v AND e)','true').replace('(v AND f)','true').replace('(v AND g)','true').replace('(v AND i)','true').replace('(v AND h)','true').replace('(v AND j)','true').replace('(v AND k)','true').replace('(v AND l)','true').replace('(v AND m)','true').replace('(v AND n)','true').replace('(v AND o)','true').replace('(v AND p)','true').replace('(v AND q)','true').replace('(v AND r)','true').replace('(v AND s)','true').replace('(v AND t)','true').replace('(v AND u)','true').replace('(v AND v)','true').replace('(v AND w)','true').replace('(v AND x)','true').replace('(v AND y)','true').replace('(v AND z)','true').replace('(!v AND v)','false').replace('(v AND !v)','true').replace('(!v AND !v)','true').replace('!(v AND !v)','true').replace('!(!v AND !v)','true').replace('!(v AND !v)','true').replace('!(!v AND !v)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(w AND !w)','false').replace('(w AND a)','true').replace('(w AND b)','true').replace('(w AND c)','true').replace('(w AND d)','true').replace('(w AND e)','true').replace('(w AND f)','true').replace('(w AND g)','true').replace('(w AND i)','true').replace('(w AND h)','true').replace('(w AND j)','true').replace('(w AND k)','true').replace('(w AND l)','true').replace('(w AND m)','true').replace('(w AND n)','true').replace('(w AND o)','true').replace('(w AND p)','true').replace('(w AND q)','true').replace('(w AND r)','true').replace('(w AND s)','true').replace('(w AND t)','true').replace('(w AND u)','true').replace('(w AND v)','true').replace('(w AND w)','true').replace('(w AND x)','true').replace('(w AND y)','true').replace('(w AND z)','true').replace('(!w AND w)','false').replace('(w AND !w)','true').replace('(!w AND !w)','true').replace('!(w AND !w)','true').replace('!(!w AND !w)','true').replace('!(w AND !w)','true').replace('!(!w AND !w)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(x AND !x)','false').replace('(x AND a)','true').replace('(x AND b)','true').replace('(x AND c)','true').replace('(x AND d)','true').replace('(x AND e)','true').replace('(x AND f)','true').replace('(x AND g)','true').replace('(x AND i)','true').replace('(x AND h)','true').replace('(x AND j)','true').replace('(x AND k)','true').replace('(x AND l)','true').replace('(x AND m)','true').replace('(x AND n)','true').replace('(x AND o)','true').replace('(x AND p)','true').replace('(x AND q)','true').replace('(x AND r)','true').replace('(x AND s)','true').replace('(x AND t)','true').replace('(x AND u)','true').replace('(x AND v)','true').replace('(x AND w)','true').replace('(x AND x)','true').replace('(x AND y)','true').replace('(x AND z)','true').replace('(!x AND x)','false').replace('(x AND !x)','true').replace('(!x AND !x)','true').replace('!(x AND !x)','true').replace('!(!x AND !x)','true').replace('!(x AND !x)','true').replace('!(!x AND !x)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(y AND !y)','false').replace('(y AND a)','true').replace('(y AND b)','true').replace('(y AND c)','true').replace('(y AND d)','true').replace('(y AND e)','true').replace('(y AND f)','true').replace('(y AND g)','true').replace('(y AND i)','true').replace('(y AND h)','true').replace('(y AND j)','true').replace('(y AND k)','true').replace('(y AND l)','true').replace('(y AND m)','true').replace('(y AND n)','true').replace('(y AND o)','true').replace('(y AND p)','true').replace('(y AND q)','true').replace('(y AND r)','true').replace('(y AND s)','true').replace('(y AND t)','true').replace('(y AND u)','true').replace('(y AND v)','true').replace('(y AND w)','true').replace('(y AND x)','true').replace('(y AND y)','true').replace('(y AND z)','true').replace('(!y AND y)','false').replace('(y AND !y)','true').replace('(!y AND !y)','true').replace('!(y AND !y)','true').replace('!(!y AND !y)','true').replace('!(y AND !y)','true').replace('!(!y AND !y)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(z AND !z)','false').replace('(z AND a)','true').replace('(z AND b)','true').replace('(z AND c)','true').replace('(z AND d)','true').replace('(z AND e)','true').replace('(z AND f)','true').replace('(z AND g)','true').replace('(z AND i)','true').replace('(z AND h)','true').replace('(z AND j)','true').replace('(z AND k)','true').replace('(z AND l)','true').replace('(z AND m)','true').replace('(z AND n)','true').replace('(z AND o)','true').replace('(z AND p)','true').replace('(z AND q)','true').replace('(z AND r)','true').replace('(z AND s)','true').replace('(z AND t)','true').replace('(z AND u)','true').replace('(z AND v)','true').replace('(z AND w)','true').replace('(z AND x)','true').replace('(z AND y)','true').replace('(z AND z)','true').replace('(!z AND z)','false').replace('(z AND !z)','true').replace('(!z AND !z)','true').replace('!(z AND !z)','true').replace('!(!z AND !z)','true').replace('!(z AND !z)','true').replace('!(!z AND !z)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false');
}
if(booleanExpression === "true"){document.write('true');}
else if(booleanExpression === "false"){document.write('false');}
else{document.write("true");}

​There is over 1000 different possible replacements and it definitely in constant time as described by https://en.wikipedia.org/wiki/Time_complexity
I have only used nand gates though but that should be okay since all boolean circuits can be represented with nand gates. You have to use replace for it to work properly on a deterministic turing machine where each replacement is a value in the state configuration table. We can actually limit the above to just and still have the answer work out correct.

booleanExpression = booleanExpression.replace('(a AND !a)','false').replace('(a AND a)','true').replace('(a AND b)','true').replace('(!a AND a)','false').replace('(a AND !a)','true').replace('(!a AND !a)','true').replace('!(a AND !a)','true').replace('!(!a AND !a)','true').replace('!(a AND !a)','true').replace('!(!a AND !a)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false').replace('(b AND !b)','false').replace('(b AND a)','true').replace('(b AND b)','true').replace('(!b AND b)','false').replace('(b AND !b)','true').replace('(!b AND !b)','true').replace('!(b AND !b)','true').replace('!(!b AND !b)','true').replace('!(b AND !b)','true').replace('!(!b AND !b)','true').replace('!(true AND !true)','false').replace('!(!false AND !true)','false').replace('!(false AND !false)','true').replace('!(!false AND !false)','false').replace('!(true AND true)','false').replace('!(false AND false)','true').replace('(true AND !true)','false').replace('(true AND false)','false').replace('(true AND !false)','true').replace('(!false AND !true)','true').replace('(false AND !false)','false').replace('(!false AND !false)','true').replace('(true AND true)','true').replace('(false AND false)','false')

Since it is a heuristic it will sometimes get things wrong. It is possible to work out if it could be wrong. In which case you either have to test or improve the heuristic with more replacements.

for(var i = 0; i < 4; i = i +1){
    booleanExpression = booleanExpression.replace('(a AND !a)','false');
    booleanExpression = booleanExpression.replace('(!a AND a)','false');
    booleanExpression = booleanExpression.replace('!(a AND !a)','true');
    booleanExpression = booleanExpression.replace('!(!a AND a)','true');
    booleanExpression = booleanExpression.replace('(b AND !b)','false');
    booleanExpression = booleanExpression.replace('(!b AND b)','false');
    booleanExpression = booleanExpression.replace('!(b AND !b)','true');
    booleanExpression = booleanExpression.replace('!(!b AND b)','true');
    booleanExpression = booleanExpression.replace('(c AND !c)','false');
    booleanExpression = booleanExpression.replace('(!c AND c)','false');
    booleanExpression = booleanExpression.replace('!(c AND !c)','true');
    booleanExpression = booleanExpression.replace('!(!c AND c)','true');
    booleanExpression = booleanExpression.replace('(d AND !d)','false');
    booleanExpression = booleanExpression.replace('(!d AND d)','false');
    booleanExpression = booleanExpression.replace('!(d AND !d)','true');
    booleanExpression = booleanExpression.replace('!(!d AND d)','true');
    booleanExpression = booleanExpression.replace('(e AND !e)','false');
    booleanExpression = booleanExpression.replace('(!e AND e)','false');
    booleanExpression = booleanExpression.replace('!(e AND !e)','true');
    booleanExpression = booleanExpression.replace('!(!e AND e)','true');
    booleanExpression = booleanExpression.replace('(f AND !f)','false');
    booleanExpression = booleanExpression.replace('(!f AND f)','false');
    booleanExpression = booleanExpression.replace('!(f AND !f)','true');
    booleanExpression = booleanExpression.replace('!(!f AND f)','true');
    booleanExpression = booleanExpression.replace('(g AND !g)','false');
    booleanExpression = booleanExpression.replace('(!g AND g)','false');
    booleanExpression = booleanExpression.replace('!(g AND !g)','true');
    booleanExpression = booleanExpression.replace('!(!g AND g)','true');
    booleanExpression = booleanExpression.replace('(h AND !h)','false');
    booleanExpression = booleanExpression.replace('(!h AND h)','false');
    booleanExpression = booleanExpression.replace('!(h AND !h)','true');
    booleanExpression = booleanExpression.replace('!(!h AND h)','true');
    booleanExpression = booleanExpression.replace('(i AND !i)','false');
    booleanExpression = booleanExpression.replace('(!i AND i)','false');
    booleanExpression = booleanExpression.replace('!(i AND !i)','true');
    booleanExpression = booleanExpression.replace('!(!i AND i)','true');
    booleanExpression = booleanExpression.replace('(j AND !j)','false');
    booleanExpression = booleanExpression.replace('(!j AND j)','false');
    booleanExpression = booleanExpression.replace('!(j AND !j)','true');
    booleanExpression = booleanExpression.replace('!(!j AND j)','true');
    booleanExpression = booleanExpression.replace('(k AND !k)','false');
    booleanExpression = booleanExpression.replace('(!k AND k)','false');
    booleanExpression = booleanExpression.replace('!(k AND !k)','true');
    booleanExpression = booleanExpression.replace('!(!k AND k)','true');
    booleanExpression = booleanExpression.replace('(l AND !l)','false');
    booleanExpression = booleanExpression.replace('(!l AND l)','false');
    booleanExpression = booleanExpression.replace('!(l AND !l)','true');
    booleanExpression = booleanExpression.replace('!(!l AND l)','true');
    booleanExpression = booleanExpression.replace('(m AND !m)','false');
    booleanExpression = booleanExpression.replace('(!m AND m)','false');
    booleanExpression = booleanExpression.replace('!(m AND !m)','true');
    booleanExpression = booleanExpression.replace('!(!m AND m)','true');
    booleanExpression = booleanExpression.replace('(n AND !n)','false');
    booleanExpression = booleanExpression.replace('(!n AND n)','false');
    booleanExpression = booleanExpression.replace('!(n AND !n)','true');
    booleanExpression = booleanExpression.replace('!(!n AND n)','true');
    booleanExpression = booleanExpression.replace('(o AND !o)','false');
    booleanExpression = booleanExpression.replace('(!o AND o)','false');
    booleanExpression = booleanExpression.replace('!(o AND !o)','true');
    booleanExpression = booleanExpression.replace('!(!o AND o)','true');
    booleanExpression = booleanExpression.replace('(p AND !p)','false');
    booleanExpression = booleanExpression.replace('(!p AND p)','false');
    booleanExpression = booleanExpression.replace('!(p AND !p)','true');
    booleanExpression = booleanExpression.replace('!(!p AND p)','true');
    booleanExpression = booleanExpression.replace('(q AND !q)','false');
    booleanExpression = booleanExpression.replace('(!q AND q)','false');
    booleanExpression = booleanExpression.replace('!(q AND !q)','true');
    booleanExpression = booleanExpression.replace('!(!q AND q)','true');
    booleanExpression = booleanExpression.replace('(r AND !r)','false');
    booleanExpression = booleanExpression.replace('(!r AND r)','false');
    booleanExpression = booleanExpression.replace('!(r AND !r)','true');
    booleanExpression = booleanExpression.replace('!(!r AND r)','true');
    booleanExpression = booleanExpression.replace('(s AND !s)','false');
    booleanExpression = booleanExpression.replace('(!s AND s)','false');
    booleanExpression = booleanExpression.replace('!(s AND !s)','true');
    booleanExpression = booleanExpression.replace('!(!s AND s)','true');
    booleanExpression = booleanExpression.replace('(t AND !t)','false');
    booleanExpression = booleanExpression.replace('(!t AND t)','false');
    booleanExpression = booleanExpression.replace('!(t AND !t)','true');
    booleanExpression = booleanExpression.replace('!(!t AND t)','true');
    booleanExpression = booleanExpression.replace('(u AND !u)','false');
    booleanExpression = booleanExpression.replace('(!u AND u)','false');
    booleanExpression = booleanExpression.replace('!(u AND !u)','true');
    booleanExpression = booleanExpression.replace('!(!u AND u)','true');
    booleanExpression = booleanExpression.replace('(v AND !v)','false');
    booleanExpression = booleanExpression.replace('(!v AND v)','false');
    booleanExpression = booleanExpression.replace('!(v AND !v)','true');
    booleanExpression = booleanExpression.replace('!(!v AND v)','true');
    booleanExpression = booleanExpression.replace('(w AND !w)','false');
    booleanExpression = booleanExpression.replace('(!w AND w)','false');
    booleanExpression = booleanExpression.replace('!(w AND !w)','true');
    booleanExpression = booleanExpression.replace('!(!w AND w)','true');
    booleanExpression = booleanExpression.replace('(x AND !x)','false');
    booleanExpression = booleanExpression.replace('(!x AND x)','false');
    booleanExpression = booleanExpression.replace('!(x AND !x)','true');
    booleanExpression = booleanExpression.replace('!(!x AND x)','true');
    booleanExpression = booleanExpression.replace('(y AND !y)','false');
    booleanExpression = booleanExpression.replace('(!y AND y)','false');
    booleanExpression = booleanExpression.replace('!(y AND !y)','true');
    booleanExpression = booleanExpression.replace('!(!y AND y)','true');
    booleanExpression = booleanExpression.replace('(x AND !x)','false');
    booleanExpression = booleanExpression.replace('(!x AND x)','false');
    booleanExpression = booleanExpression.replace('!(x AND !x)','true');
    booleanExpression = booleanExpression.replace('!(!x AND x)','true');
    booleanExpression = booleanExpression.replace('!(true AND !true)','false');
    booleanExpression = booleanExpression.replace('!(!false AND !true)','false');
    booleanExpression = booleanExpression.replace('!(false AND !false)','true');
    booleanExpression = booleanExpression.replace('!(!false AND !false)','false');
    booleanExpression = booleanExpression.replace('!(true AND true)','false');
    booleanExpression = booleanExpression.replace('!(false AND false)','true');
    booleanExpression = booleanExpression.replace('(true AND !true)','false');
    booleanExpression = booleanExpression.replace('(true AND false)','false');
    booleanExpression = booleanExpression.replace('(true AND !false)','true');
    booleanExpression = booleanExpression.replace('(!false AND !true)','true');
    booleanExpression = booleanExpression.replace('(false AND !false)','false');
    booleanExpression = booleanExpression.replace('(!false AND !false)','true');
    booleanExpression = booleanExpression.replace('(true AND true)','true');
    booleanExpression = booleanExpression.replace('(false AND false)','false');
}
if(booleanExpression === "true"){document.write('true');}
else if(booleanExpression === "false"){document.write('false');}
else{
    if(booleanExpression.length<originalbooleanExpression.length){
        document.write("test");
    } else {
        document.write("true");
    }
}
    document.write(booleanExpression);
Edited by fiveworlds
-2
Link to comment
Share on other sites
fiveworlds

fiveworlds

Posted
  • Author
Posted (edited)
If you are not interested in discussing this, what is the point of this thread? Just another demonstration of how little you understand?​

 

 

Then why are you talking about it? I thought up of a much faster algorithm for boolean sat.

<script>
 var str = "((((((((A and B)AND(A and !B))AND(!A and B))!AND(A and A))AND(A and !B))!)AND(A and !B))!)";
 var letters = ['A','B'], lastIndex = 0, countright = 0, satisfiability = ['false','true'];
 for(var i = 0; i < letters.length; i = i + 1){
  if((str.lastIndexOf(letters[i]) !=-1) && (str.lastIndexOf("!"+letters[i]) != -1)){
   if(str.lastIndexOf("!"+letters[i])>str.lastIndexOf(letters[i])){
    if(lastIndex < str.lastIndexOf(letters[i]))
    {
     lastIndex = str.lastIndexOf(letters[i]);
     satisfiability = ['false','true']
    };
   } else if (lastIndex <  str.lastIndexOf("!"+letters[i])){
    lastIndex = str.lastIndexOf("!"+letters[i]);
    satisfiability = ['false','true']
   }
   
   if(str.lastIndexOf(letters[i]+" AND " + letters[i]) > lastIndex){
    lastIndex = str.lastIndexOf(letters[i]+" AND " + letters[i]);
    satisfiability = ['true','false'];
   }
  }
 }
 while(countright < 2){
  if(str.charAt(lastIndex)==')'){countright = countright + 1;}
  lastIndex = lastIndex + 1;
 }
 
 str = str.substr(lastIndex - 1);
 var count = str.length;
 while(str.indexOf(")!)") != -1) {
  str = str.replace(")!)","))");
 }
 count = count - str.length;
 document.write((count % 2 == 0)? satisfiability[0] : satisfiability[1]);
</script>
Edited by fiveworlds
Link to comment
Share on other sites
Strange

Strange

Posted
Posted

 

 

 

Then why are you talking about it?

 

 

I thought you might want to explain what you are doing, show the calculations and, you know, discuss it. What with this being a discussion forum.

 

If all you want to do is make implausible claims and post code samples, then I suggest a blog.

Link to comment
Share on other sites
fiveworlds

fiveworlds

Posted
  • Author
Posted (edited)
What do you mean by "SAT"?

 

 

https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

 

I mean the boolean satisfiability problem as we can see from the Deterministic Turing Macine Finite State Machine State Configuration Table below we need only one movement from right to left to run the last equation. There it has a worst case runtime of O(N) which can be simplified to O(1) with a reader that can read strings of size n. Since the states for strings are fairly complicated as in millions of possibilities I'll just use a shorthand arrow notation. A -> last index of !A etc.

 

P7PxN1J.png

The main reasoning behind it is that all logic gates can be represented by NAND gates and NAND gates can be represented as NOT(A AND B). Which left me to conclude that the only time a circuit is always false is in instances where A AND NOT A are in the same circuit and all the circuits between them automatically become false as a result. So if I find the last instance where it is always false and it has a ! then it can be true for instance (((A AND NOT B) AND (A AND B))!). Then you need to count all the NOT gates between that instance and the output and it flips between true and false which is basically just odd or even. Also you are not allowed to use !(A and A) to make a different circuit that is always false since it can be simulated using one !.

Edited by fiveworlds
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share
Go to topic listing
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.