2
$\begingroup$

Many intractable $NP$-complete problems can be modeled as deciding whether a set of triples, $F=${$t_1, t_2, ..., t_n$} where each triple $t_i$ is a subset of three elements over base set $U=${$a_1, a_2, ..., a_k$}, satisfy some non-trivial property. For example, 3-edge coloring of cubic graphs can be modeled as the problem of deciding whether sets of triples satisfy that the elements in each triple must have different color.

I'm looking for examples of non-trivial tractable properties ($P_2$) of sets of triples (which have polynomial time algorithms) given that the sets of triples already satisfies some other non-trivial property $P_1$. Non-trivial property means that there are infinite number of sets of triples that satisfy the property and infinite number of sets of triples that do not. Are all non-trivial properties $P_2$ of sets of triples intractable?

Also, I'd appreciate a survey on the subject.

EDIT: Based on Ben's answer, I added the requirement that $F$ already satisfies some non-trivial property $P_1$ and we are asking weather it satisfies another no-trivial property $P_2$. For instance, in the 3-edge coloring example, the family of triples $F$ must represent the edges incident on the nodes of a cubic graph.

$\endgroup$
  • 1
    $\begingroup$ This question is incredibly broad and vague. What would you consider a "triple" in this context? $\endgroup$ – Raphael Mar 22 '12 at 23:10
  • $\begingroup$ A triple could be a set of three integers {$i_1, i_2, i_3$}. $\endgroup$ – Mohammad Al-Turkistany Mar 22 '12 at 23:15
  • $\begingroup$ Another intractable example of triples is the satisfiability of monotone 1-in-3 SAT. However, I'm looking for tractable properties. $\endgroup$ – Mohammad Al-Turkistany Mar 22 '12 at 23:22
  • $\begingroup$ Yet another example is the NP-complete problem 3-Set Splitting problem. $\endgroup$ – Mohammad Al-Turkistany Mar 22 '12 at 23:28
  • $\begingroup$ I assume you want to distill out what makes NP-hard problems (allegedly) hard. You do not seem to be even close to the essence as you do not require $P_2$ to be non-local in any sense. See also Ben's answer. $\endgroup$ – Raphael Mar 23 '12 at 0:53
3
$\begingroup$

I think your "non-trivial" property would need to be a property of sets of triples, not of triples themselves; i.e. you need that there are an infinite number of sets of triples that satisfy and do not satisfy the property.

Call a triple consists of 3 identical elements a 3-clone. Checking that a triple is a 3-clone can obviously be done in linear time, and checking that a set of triples are all 3-clones can also be done in linear time, because checking each triple is independent of every other triple. And there are an infinite number of 3-clones, and an infinite number of non-3-clone triples; so straightforwardly there are infinite numbers of sets of 3-clones and sets that aren't sets of 3-clones.

I think you need to strengthen the definition of non-triviality; any property of triples that is non-trivial can be lifted to a fairly boring non-trivial property of sets of triples, and there are lots of non-trivial properties of triples that are trivially easy to decide. Even the property of whether the first element of the triple is 1 works. I think the "interesting" properties of sets of triples are not just independently decidable for each triple and then combining the decisions. I'm not sure how to go about expressing that constraint in a rigorous way though.

As for a survey on the subject, I'm afraid I'd never heard of characterising NP-complete problems as properties of sets of triples, so I can't do much for you there.

$\endgroup$
  • $\begingroup$ Thanks Ben for your suggestions. I edited the question accordingly. $\endgroup$ – Mohammad Al-Turkistany Mar 23 '12 at 0:16
1
$\begingroup$

Let $S \subseteq \mathbb{N}^3$ with $|S| < \infty$ and $P_1(S)$ where

$\quad \displaystyle P_1(S)\ \ :\Longleftrightarrow\ \ \forall (i,j,k)\in S. i,j,k \text{ mutually coprime }.$

$P_1$ is clearly non-trivial as requested. We say furthermore

$\quad \displaystyle P_2(S)\ \ :\Longleftrightarrow\ \ \forall (i,j,k)\in S.\ i + j + k \text{ prime}.$

Clearly, $P_2$ is non-trivial as there are both infinitely many primes and non-primes ($2\mathbb{N}$).

$P_2$ is decidable in polynomial time as $S$ is finite and both addition and check for primality are polynomial.

As requested, consider this small example of a set of triples that fulfills $P_1$ and $P_2$:

$\quad \{(1,3,7),(1,5,7),(1,5,11),(1,3,13),(5,7,19)\}$

$\endgroup$
  • $\begingroup$ An element of $L$ should be a subset of triples not just one triple as in your example. See the intractable examples I mentioned in my comments. $\endgroup$ – Mohammad Al-Turkistany Mar 22 '12 at 23:34
  • $\begingroup$ You explicitly ask for properties of triples; this is one. You can also view $L$ as set of singleton triple sets, if you want. I guess you should rephrase your question carefully? $\endgroup$ – Raphael Mar 22 '12 at 23:37
  • $\begingroup$ @MohammadAl-Turkistany: Edited answer accordingly. $\endgroup$ – Raphael Mar 23 '12 at 0:28
  • $\begingroup$ Sorry Raphael, I edited the question again. Hope it is fine with you. $\endgroup$ – Mohammad Al-Turkistany Mar 23 '12 at 0:34
  • $\begingroup$ @MohammadAl-Turkistany: Adapted again. Note that you can add as many shallow requirements as you want; there are many easy triple-properties. $\endgroup$ – Raphael Mar 23 '12 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.