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.

  • 1
    $\begingroup$ This question is incredibly broad and vague. What would you consider a "triple" in this context? $\endgroup$
    – Raphael
    Mar 22, 2012 at 23:10
  • $\begingroup$ A triple could be a set of three integers {$i_1, i_2, i_3$}. $\endgroup$ Mar 22, 2012 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$ Mar 22, 2012 at 23:22
  • $\begingroup$ Yet another example is the NP-complete problem 3-Set Splitting problem. $\endgroup$ Mar 22, 2012 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, 2012 at 0:53

2 Answers 2


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.

  • $\begingroup$ Thanks Ben for your suggestions. I edited the question accordingly. $\endgroup$ Mar 23, 2012 at 0:16

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)\}$

  • $\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$ Mar 22, 2012 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, 2012 at 23:37
  • $\begingroup$ @MohammadAl-Turkistany: Edited answer accordingly. $\endgroup$
    – Raphael
    Mar 23, 2012 at 0:28
  • $\begingroup$ Sorry Raphael, I edited the question again. Hope it is fine with you. $\endgroup$ Mar 23, 2012 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, 2012 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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