<p>I am currently working on some property defined in the following way. Let <span class="math-container">$S$</span> be a set of positive integers. We say that <span class="math-container">$S$</span> has the property <span class="math-container">$P$</span> iff one of the following two conditions holds.</p>
<ol>
<li>This set <span class="math-container">$S$</span> is a singleton.</li>
<li>For every <span class="math-container">$x \in \{1,…,\lfloor \frac{|S|}{2} \rfloor\}$</span>, there exists a partition of <span class="math-container">$S$</span> into two parts <span class="math-container">$S_1$</span> and <span class="math-container">$S_2$</span> such that their sizes are <span class="math-container">$x$</span> and <span class="math-container">$|S|-x$</span>, respectively, and they both satisfy the property <span class="math-container">$P$</span>.</li>
</ol>
<p>In other words, <span class="math-container">$S$</span> has the property <span class="math-container">$P$</span> iff it can always be partitioned into two subsets of arbitrary sizes having the property <span class="math-container">$P$</span> themselves.</p>
<p>Now, I would like to consider the complexity of the associated decision problem.</p>
<blockquote>
<p>P-PROPERTY</p>
<p>Instance: A set <span class="math-container">$S$</span> of positive integers.</p>
<p>Question: Does <span class="math-container">$S$</span> have the property <span class="math-container">$P$</span>?</p>
</blockquote>
<p>At first sight, such a problem belongs neither to NP nor to co-NP (does it?). Moreover, because of the recursivity, I do not see how this problem could belong to the polynomial hierarchy.</p>
<p>I never saw a problem recursively defined like this one, that is why I am getting some trouble dealing with it. So, is there a way to deal with the complexity of such a problem?</p>
<p>Thanks in advance (and sorry if the answer is obvious :o) )!</p>

CC BY-SA 3.0
2012-07-24T12:27:05.633Z
Condition 2 does not seem to be equivalent to the sentence _"$S$ has the property $P$ if and only if it can always be partitioned into 2 subsets of arbitrary sizes having the property $P$ themselves"_. Condition 2 says $\forall x$..., while the above sentence seems to say $\exists x$...
Giorgio Camerani
CC BY-SA 3.0
2012-07-24T12:47:03.307Z
If the answer is that there only has to be one partition at each level (rather than for every partition) with described conditions, and property $P$ is PTIME decidable, then the problem should be in NP. We can ask for a certificate that's something along the lines of "label each element with a string over $\{1,2\}$, which gives which partite set it is in at that recursive depth". Then we can check that the partitions satisfy $P$ easily enough.
Luke Mathieson
CC BY-SA 3.0
2012-07-24T12:52:15.203Z
In the other case, it should be in co-NP, as we can give a short certificate for a No-instances (i.e. one partition that doesn't have the property $P$).
Luke Mathieson
CC BY-SA 3.0
2012-07-24T13:01:56.930Z
Every finite set has property $P$ (prove it by induction). If $S$ is infinite then your definition doesn't really make sense (for several reasons), so I presume the domain you were looking at was finite sets, and for that domain, every set has property $P$.
Yuval Filmus
CC BY-SA 3.0
2012-07-24T13:33:58.053Z
Of course! Too busy thinking about complexity, not enough about the actual property.
Luke Mathieson
CC BY-SA 3.0
2012-07-24T15:34:59.307Z
Well, I tried to give an overview of the property using sets to show off its recursive aspect, but the problem I am actually working on deals with graphs. 

A graph G is said to be R-AP (recursively arbitrarily partitionable) iff one of the two conditions holds.

1. The graph is an isolated vertex.
2. For every $x \in \{1, ..., \lfloor \frac{|V(G)|}{2} \rfloor \}$ there exists a partition $(V_1, V_2)$ of $V(G)$ such that $G[V_1]$ and $G[V_2]$ are connected R-AP graphs on $x$ and $n-x$ vertices, respectively.

Does it seem to be that easy when considering graphs instead of sets?
jbensmai
CC BY-SA 3.0
2012-07-24T16:14:56.783Z
Just because the definition is recursive doesn't mean that this problem is not in NP (or even P). Pratt first showed that PRIMES is in NP by a recursive process now known as the [Pratt certificate](http://en.wikipedia.org/wiki/Primality_certificate#Pratt_certificates) that I think sounds similar to your problem.
Tyson Williams
CC BY-SA 3.0
2012-07-24T19:20:23.130Z
@Tyson Naively, the witness is superpolynomial in size, probably $n^{\log n}$.
Yuval Filmus
CC BY-SA 3.0
2012-07-24T19:21:17.450Z
@jbensmai, you should rephrase your question, and add links to relevant papers (to motivate the notion, at the very least).
Yuval Filmus
<cc.complexity-theory><co.combinatorics><complexity-classes><property-testing>
Catching the complexity of determining some recursively defined property
jbensmai
# Catching the complexity of determining some recursively defined property

(Asked by: username_0 on 2012-07-24)

I am currently working on some property defined in the following way. Let $S$ be a set of positive integers. We say that $S$ has the property $P$ iff one of the following two conditions holds.

1. This set $S$ is a singleton.
2. For every $x \in \{1,…,\lfloor \frac{|S|}{2} \rfloor\}$, there exists a partition of $S$ into two parts $S\_1$ and $S\_2$ such that their sizes are $x$ and $|S|-x$, respectively, and they both satisfy the property $P$.

In other words, $S$ has the property $P$ iff it can always be partitioned into two subsets of arbitrary sizes having the property $P$ themselves.

Now, I would like to consider the complexity of the associated decision problem.

> P-PROPERTY
>
> Instance: A set $S$ of positive integers.
>
> Question: Does $S$ have the property $P$?

At first sight, such a problem belongs neither to NP nor to co-NP (does it?). Moreover, because of the recursivity, I do not see how this problem could belong to the polynomial hierarchy.

I never saw a problem recursively defined like this one, that is why I am getting some trouble dealing with it. So, is there a way to deal with the complexity of such a problem?

Thanks in advance (and sorry if the answer is obvious :o) )!

**Tags:** cc.complexity-theory, co.combinatorics, complexity-classes, property-testing
> **Comments:**
> **username_1**: Condition 2 does not seem to be equivalent to the sentence _"$S$ has the property $P$ if and only if it can always be partitioned into 2 subsets of arbitrary sizes having the property $P$ themselves"_. Condition 2 says $\forall x$..., while the above sentence seems to say $\exists x$...  
> **username_2**: If the answer is that there only has to be one partition at each level (rather than for every partition) with described conditions, and property $P$ is PTIME decidable, then the problem should be in NP. We can ask for a certificate that's something along the lines of "label each element with a string over $\{1,2\}$, which gives which partite set it is in at that recursive depth". Then we can check that the partitions satisfy $P$ easily enough.  
> **username_2**: In the other case, it should be in co-NP, as we can give a short certificate for a No-instances (i.e. one partition that doesn't have the property $P$).  
> **username_3**: Every finite set has property $P$ (prove it by induction). If $S$ is infinite then your definition doesn't really make sense (for several reasons), so I presume the domain you were looking at was finite sets, and for that domain, every set has property $P$.  
> **username_2**: Of course! Too busy thinking about complexity, not enough about the actual property.  
> **username_0**: Well, I tried to give an overview of the property using sets to show off its recursive aspect, but the problem I am actually working on deals with graphs.   A graph G is said to be R-AP (recursively arbitrarily partitionable) iff one of the two conditions holds.  1. The graph is an isolated vertex. 2. For every $x \in \{1, ..., \lfloor \frac{|V(G)|}{2} \rfloor \}$ there exists a partition $(V_1, V_2)$ of $V(G)$ such that $G[V_1]$ and $G[V_2]$ are connected R-AP graphs on $x$ and $n-x$ vertices, respectively.  Does it seem to be that easy when considering graphs instead of sets?  
> **username_4**: Just because the definition is recursive doesn't mean that this problem is not in NP (or even P). Pratt first showed that PRIMES is in NP by a recursive process now known as the [Pratt certificate](http://en.wikipedia.org/wiki/Primality_certificate#Pratt_certificates) that I think sounds similar to your problem.  
> **username_3**: @Tyson Naively, the witness is superpolynomial in size, probably $n^{\log n}$.  
> **username_3**: @jbensmai, you should rephrase your question, and add links to relevant papers (to motivate the notion, at the very least).  

---

## 0 answers

