Non-trivial tractable properties of triples

Question

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.

Answer 1

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.

Answer 2

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