# an unsolved problem......

• Sep 11th 2009, 07:34 PM
Khonics89
an unsolved problem......
Given a boolean expression in variables x1,x2......xn. How quickly can we determine whether the expression ever take the value 1?

At first sight the time appears to be proportional to 2^n?

We would like to find a method whose running time depends on a power of n or else prove that this is not possible.
• Sep 12th 2009, 04:47 AM
awkward
Quote:

Originally Posted by Khonics89
Given a boolean expression in variables x1,x2......xn. How quickly can we determine whether the expression ever take the value 1?

At first sight the time appears to be proportional to 2^n?

We would like to find a method whose running time depends on a power of n or else prove that this is not possible.

This is the Satisfiability Problem (SAT). See

Boolean satisfiability problem - Wikipedia, the free encyclopedia

It is known to be NP-complete, so there is no polynomial-time algorithm for its solution unless P=NP, which seems unlikely, but has not been proven impossible.