Approach 1: Brute Force

• Effectively the Brute Force Approach is the best known.
• On one processor, method runs in time roughly proportional to 2^N, where N is the number of variables and terms in an expression.
• On unlimited processors, could try one allocation of variables for each processor.
  • Each processor evaluates its expression.
  • Processors report in a tree structure.
  • Parallel method runs in time proportional to N² approximately.

Brute Force Approach for the Satisfiability Problem an example of an entire class of problems.

Three Definitions:

• A problem is said to be in Class P if it has a solution that runs on one processor in time that is a polynomial.
• A problem is said to be in Class NP if it has a solution that runs on many processors in time that is polynomial.
• A problem A is said to be NP Complete if
  • A is in Class NP, so it has a solution S that runs in polynomial time using as many processors as needed.
  • Given any problem B in Class NP, S can be transformed to a solution to problem B in polynomial time (on one processor).

Notes:

• Every problem in Class P is also in Class NP. (Why?)
• The Brute Force Approach for the Satisfiability Problem is in Class NP, but no solution is known that runs in polynomial time on one processor.
• The Satisfiability Problem is known to be NP Complete.
• If a solution for the Satisfiability Problem were found that runs in polynomial time on one processor, then we would have polynomial-time solutions with one processor for all problems in class NP. In other words,

• Many computer scientists believe that Classes P and NP are different, but no proof or example exists.
• Assuming Class P ≠ Class NP, then problems such as the Satisfiability Problem do not have feasible solutions for data sets of any size.

Final Notes regarding Efficiency:

• For some problems (e.g., Regular Expression Non-universality Problem), some solutions are known to require exponential time (or more) when run on one processor. (Today, I focused on the Satisfiability Problem, since it is easier to understand, and I wanted to mention NP Complete problems.)
• Thus, some problems are know to have only non-feasible solutions.

created 3 January 2007 last revised 10 January 2007

previous   next