X3SAT Question
- From: "Russell Easterly" <logiclab@xxxxxxxxxxx>
- Date: Mon, 7 Nov 2005 19:43:19 -0800
I have been studying the exclusive 3SAT problem (X3SAT),
also known as the 1 in 3 SAT problem.
Given a collection of clauses, where each clause contains
exactly three literals, is there a set of literals such that
each clause contains exactly one member from the set?
I am particularly interested in "reduced" X3SAT instances.
There are reduction rules that guarantee that, in a reduced instance,
no two clauses share more than one variable in common.
For simplicity, I am looking at instances that don't contain
any negated variables. It is well known that X3SAT is NP-Complete
even when there are no negated variables.
I want to find an unsatisfiable reduced X3SAT instance.
I can't prove that all unnegated reduced X3SAT instances are solvable,
but I haven't yet been able to prove that they aren't always solvable,
either.
It should be simple to prove they aren't always solvable.
Just produce a reduced X3SAT instance that is unsatifiable.
But, I haven't been able to come up with such an instance.
I would appreciate any help finding such an instance.
The instance should have the following properties:
1) No variable is negated.
2) No two clauses share more than one variable in common.
3) The instance is unsatisfiable.
This is an example of an instance that meets the first two criteria:
(a,b,c)(a,d,e)(b,d,f)(c,e,f)
The set (a,f) is one of the many solutions to this instance.
Coming up with an unsatisfiable reduced X2SAT instance is easy:
(a,b)(b,c)(a,c) in unsatisfiable.
Again, any help will be appreciated.
Russell
- 2 many 2 count
.
- Follow-Ups:
- Re: X3SAT Question
- From: RickO
- Re: X3SAT Question
- Prev by Date: Re: Does random number really exist?
- Next by Date: Is P=NP? Thought process approach.
- Previous by thread: Implementing a graph algebra
- Next by thread: Re: X3SAT Question
- Index(es):
Relevant Pages
|
