score:2
Accepted answer
1 With the obligatory "unless
I am concerned that this is overly complicated. Is there a better way?
The short answer is "No, there isn't" 1
The long answer: The "overly complicated" captures the essence of the problem: it is NP-hard. Here is a short informal proof relying upon the fact that the satisfiability problem is NP-complete:
- Suppose that you have two Boolean formulas,
AandB - You need to test if
AimpliesB, or equivalently¬A | Bfor all assignments of variables upon whichAandBdepend. In other words, you need a proof thatF = ¬A | Bis a tautology. - Suppose that the tautology test can be performed in polynomial time
- Consider
¬F, the inverse ofF.Fis satisfiable if and only if¬Fis not a tautology - Use the hypothetical polynomial algorithm to test
¬Ffor being a tautology - The answer to "is
Fsatisfiable" is the inverse of the answer to "is¬Fa tautology" - Therefore, an existence of a polynomial tautology checker would imply that the satisfiability problem is in
P, and thatP=NP.
Of course the fact that the problem is NP-hard does not mean that there would be no solutions for practical cases: in fact, your approach with the conversion to a canonical form may produce OK results in many real-world situations. However, an absence of a known "good" algorithm often discourages active development of practical solutions2.
1 With the obligatory "unless
P=NP" disclaimer.
2 Unless a "reasonably good" solution would do, which may very well be the case for your problem, if you allow for "false negatives".
Source: stackoverflow.com
Related Articles
- Extending LINQ-based Specification Pattern to implement subsumption
- Is there a suggested pattern for using LINQ between the Model & DataAccess Layers in a DDD based Layered Architecture
- Using Specification Pattern and Expressions in Entity Framework and Linq to Entities
- LINQ Source Code Available
- Can LINQ expression classes implement the observer pattern instead of deferred execution?
- creating Linq to sqlite dbml from DbLinq source code
- Linq sub query when using a repository pattern with EF code first
- Using Linq expressions as a specification pattern with parent/child query
- source code for LINQ 101 samples
- "The parameter was not bound in the specified LINQ to Entities query expression." Specification Pattern And
- How to do condition statement in LINQ based on code variables?
- LINQ expressions can not be translated to Sql when combining specifications in Specification Pattern
- Use LINQ expressions or Specification pattern to access Ingres database?
- How to write C# LINQ code to select based on condition
- What's the convention for extending Linq datacontext with set based helper operations specific to one collection of entities only
- c# Linq or code to extract groups from a single list of source data
- Getting InvalidCastException when trying to implement sorting in Entity Framework Code First using Linq
- Convert string[] to int[] in one line of code using LINQ
- Code equivalent to the 'let' keyword in chained LINQ extension method calls
- Distinct in Linq based on only one field of the table
- Select multiple records based on list of Id's with linq
- Linq code to select one item
- How are people unit testing code that uses Linq to SQL
- Extending LINQ to accept nullable enumerables
- Could not find an implementation of the query pattern for source type 'System.Data.Entity.DbSet'
- How can I implement NotOfType<T> in LINQ that has a nice calling syntax?
- Is there a pattern using Linq to dynamically create a filter?
- LINQ sort a flat list based on childorder
- LINQ query to perform a projection, skipping or wrapping exceptions where source throws on IEnumerable.GetNext()
- Distinct list of objects based on an arbitrary key in LINQ
- converting value types of an object to Dictionary<string, string>
- Query MongoDb from C# - using Linq .Any() with predicate
- LINQ - Accessing a column with the column name as a string parameter
- Sort varchar column starting with the first letter instead of the first character?
- Why doesn't LINQ include a `distinct` keyword?
- LINQ query on child list
- C# HashSet union on IEnumerable within LINQ Func expression does not work (possible precompiler bug)
- c# loop through linq results and update field
- Pass two values to view?
- How to compare two IEnumerable object and find files which are different and new?
- How to use Lambda to cast HashSet to string containing only object property
- Optional requirement on where clause in LINQ
- SQL query to LINQ (complex for me)
- Outer join two tables with null values
- C# - Intersection of Dictionary<int, SortedList<int, List<int>>>
- Parallel linq on floyd warshall
- Exchanging the internal letters of words
- How to use or convert T-SQL script into a function in an MVC 3 Web App?
- Use orderby using linq query
- Get all objects that have an object that matches a string
