Results 1 to 2 of 2

Math Help - an unsolved problem......

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    108

    Exclamation 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Khonics89 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One unsolved Puzzle.
    Posted in the Math Puzzles Forum
    Replies: 3
    Last Post: February 17th 2011, 09:59 PM
  2. A nice, unsolved geometry problem
    Posted in the Geometry Forum
    Replies: 3
    Last Post: February 23rd 2010, 02:20 AM
  3. Linear Programming Problem unsolved.
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 23rd 2008, 06:51 AM
  4. Unsolved Puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: September 29th 2006, 11:38 AM

Search Tags


/mathhelpforum @mathhelpforum