<p>Even for problems <em>within $\mathsf{NP}$</em>, and even assuming some reasonable notion of "natural property", there is likely no such dichotomy theorem (in addition to the excellent answers of Davids Richerby and Eppstein exhibiting natural problems much harder than $\mathsf{NP}$-complete). </p>

<p>The reason is that there are likely to be natural, interesting properties that are sparse, i.e. only $\leq poly(n)$ many cubic graphs on $n$ vertices have the property (not to be confused with "sparse" in the sense of "sparse graph," which all cubic graphs are). By Mahaney's Theorem, no such problem can be $\mathsf{NP}$-complete. (Assuming $\mathsf{P} \neq \mathsf{NP}$, but that's implicit in the question itself.)</p>

<p>I'd be grateful to anyone who could strengthen this answer by coming up with such a property: natural, interesting, and sparse.</p>

CC BY-SA 3.0
2014-01-31T23:51:14.437Z
2014-01-31T23:51:14.437Z
Joshua Grochow
<p>There is no <strong>P</strong>-vs-<strong>NP</strong> dichotomy for problems on cubic graphs because there are problems on cubic graphs of arbitrarily high complexity.  We can code arbitrary binary strings as cubic graphs, thus translating any question about binary strings into a question about cubic graphs.</p>

<p>For $k\geq 5$, let $W_k$ be the graph consisting of two disjoint $k$-cycles $x_1\dots x_k x_1$ and $y_1\dots y_k y_1$, along with the matching $x_2y_2, \dots, x_ky_k$. (Thus, every vertex except $x_1$ and $x_2$ has degree&nbsp;3.) Given an arbitrary binary string $s=s_1\dots s_\ell$, let $H_1 \dots H_{\ell+4}$ be the following sequence of graphs.  For $1\leq i\leq \ell$, let $H_i = W_5$ if $s_i=0$ and $H_i = W_7$ if $s_i=1$.  Let $H_{\ell+1}=H_{\ell+4}=W_9$, $H_{\ell+2} = W_5$ and $H_{\ell+3} = W_7$.  Now, let $G_s$ be the graph made from the sequence of $H$'s by adding an edge between a degree-2 vertex in $H_i$ and one in $H_{i+1}$ ($i&lt;\ell+4$) and likewise between $H_{\ell+4}$ and&nbsp;$H_1$, thus making a connected, cubic graph.  (The purpose of $H_{\ell+1}, \dots, H_{\ell+4}$ is just to establish the direction of the cycle.)</p>

<p>Now, take any language $\mathcal{L}\subseteq \{0,1\}^*$ &ndash; it doesn't even have to be decidable. $\mathcal{G} = \{G_s\mid s\in\mathcal{L}\}$ is a subset of the cubic graphs and determining membership of $\mathcal{G}$ has the same complexity as determining membership of $\mathcal{L}$.</p>

CC BY-SA 3.0
2014-01-30T13:30:40.637Z
What are you trying to prove with your example? Could you provide a figure to illustrate your idea?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T14:39:41.360Z
I don't see the point. There are undecidable problems in $P/poly$ which contains $P$ ($P/poly$ is considered an acceptable notion of efficiency).
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T14:45:33.307Z
You asked if there is a **P**-vs-**NP**-complete dichotomy for problems on cubic graphs. That would mean that *every* problem on cubic graphs would have to be either in **P** or be **NP**-complete (or possibly both at the same time, if **P** = **NP**). I have shown that there are problems on cubic graphs that are not even in **NP**. Such a problem cannot be **NP**-complete or in **P**, which means that your proposed dichotomy does not exist.
David Richerby
CC BY-SA 3.0
2014-01-30T14:50:17.640Z
I don't see a proof that your problem is not in $NP$. Also, as I stated in the problem, I am only interested in $NP$ properties.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T14:55:18.113Z
@MohammadAl-Turkistany "It doesn't even have to be decidable."
David Richerby
CC BY-SA 3.0
2014-01-30T13:00:25.637Z
2014-01-30T14:32:55.547Z
2014-01-30T14:32:55.547Z
David Richerby
<p>No, there is no such theorem. There cannot be such a theorem because a theorem is a formal, proven statement of mathematics and "natural interesting property" is not a formal property and, therefore, nothing can possibly be proven about it.</p>

CC BY-SA 3.0
2014-01-30T10:45:27.417Z
Thanks for your answer. I am afraid that your answer  implicitly excludes the existence of any reasonable formalization of "natural interesting property" of cubic graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T10:45:52.563Z
I'm guessing @Mohammad was looking for a definition of "natural" in the same vein as Razborov & Rudich's definition in the context of class-separation proofs. I would hazard to guess that doing this in the current context would be much more difficult, as the definition would probably need to be general enough to allow for rather complicated verifiers (so presumably it makes a claim regarding TM/circuit-like structures), yet somehow be restrictive enough to somehow avoid making claims about anything obfuscated (as classifying obfuscated circuits will be hard by definition).
Yonatan N
CC BY-SA 3.0
2014-01-30T12:23:00.103Z
@YonatanN Past experience [1](http://cstheory.stackexchange.com/q/20035/17082) [2](http://cs.stackexchange.com/q/19244/9550) indicates that "natural" means "I want to play a game of whack-a-mole where I conjecture something and then try to forbid all the trivial counter-examples that people come up with."
David Richerby
CC BY-SA 3.0
2014-01-30T08:21:09.493Z
2014-01-30T08:21:09.493Z
David Richerby
<p>Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.</p>

<p>I've made this community wiki because I think it could be a large list.</p>

<ul>
<li>Are there evenly many 3-edge-colorings? (Should be $\oplus P$-complete)</li>
<li>Who wins at strings-and-coins? (Might be PSPACE-complete)</li>
<li>What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)</li>
<li>Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)</li>
<li>Given two cubic Halin graphs with the same labeled outer face, how few steps does it take to convert one to the other by alternatingly contracting an interior edge and then uncontracting it the other way? (Equivalent to the open problem of computing rotation distance on binary search trees; might also be interesting for broader classes of cubic graphs)</li>
</ul>

CC BY-SA 3.0
2014-01-30T10:52:40.263Z
Thanks for your answer. Are your counter-examples for the class of connected cubic graphs?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T21:43:59.460Z
The whole reason I stated the first example in terms of biconnected components rather than connected components was to make it apply to connected graphs. The other problems decompose on disconnected graphs, so connected graphs are their hardest case.
David Eppstein
CC BY-SA 3.0
2014-01-31T02:39:30.837Z
@JoshuaGrochow Isn't GI in P for bounded-degree graphs?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-31T03:06:25.803Z
Oh, sorry, right. I was being oblivious.
Joshua Grochow
CC BY-SA 3.0
2014-01-31T22:05:15.860Z
Oops, yes, so getting a GI-complete problem out of cubic graphs is not going to be as easy as taking biconnected components. I'll take that one out of the list for now.
David Eppstein
CC BY-SA 3.0
2014-02-05T09:14:43.930Z
Can't you just compute the determinant of the adjacency matrix of a graph mod 2 to get the parity of the number of perfect matchings in a graph?
Andreas Björklund
CC BY-SA 3.0
2014-02-05T16:35:56.223Z
Oh, probably. I picked that one over Hamiltonian cycles because there are always an even number of Hamiltonian cycles. But one of those types of problems should be $\oplus\mathsf{P}$-complete; I guess I need to look harder for the right one.
David Eppstein
CC BY-SA 3.0
2014-02-05T18:59:15.823Z
I changed it from matchings to 3-edge-colorings for this reason.
David Eppstein
CC BY-SA 3.0
2014-01-30T07:42:38.593Z
2014-02-05T18:59:00.043Z
2014-02-05T18:59:00.043Z
David Eppstein
<p>It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem. </p>

<p>By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is <a href="https://cstheory.stackexchange.com/a/20776/495">Yutsis graph</a>). The preceding two example problems demonstrates what I mean by <strong>natural interesting property</strong> of cubic graphs.</p>

<p>Another <strong>natural interesting property</strong> of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.</p>

<p>I'm interested in a dichotomy theorem that tells us which <strong>natural interesting</strong> problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.</p>

<blockquote>
  <p>Is there a P/NP-complete dichotomy theorem for <strong>natural interesting</strong> properties of cubic graphs?</p>
</blockquote>

<p>As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. <a href="https://cstheory.stackexchange.com/questions/19845/np-complete-graph-problems-about-structural-properties">Bach's post</a> may help in clarifying my motivation. <a href="https://cstheory.stackexchange.com/a/19866/495">My answer</a> to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.</p>

<p>Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of <strong>connected</strong> cubic graphs.</p>

<p><strong>EDIT 1-30-2014</strong>:  To capture the essence of <strong>natural property</strong> of cubic graphs, I accept a natural $NP$ <strong>property</strong> $X$ of cubic graphs where there is <strong>natural</strong> efficient verifier that verifies a <strong>natural interesting</strong> relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.</p>

CC BY-SA 3.0
2014-01-29T22:44:15.790Z
Although the following does not answer the above question, I am interested in polynomial-time decidable natural interesting properties of cubic graphs. If no such examples exist, It is natural to conjecture that deciding any **natural interesting property** of cubic graphs is $NP$-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T03:04:34.180Z
Interesting question! But in order to get a dichotomy theorem I think one would have to pick a defn of "natural interesting property." Maybe isomorphism-invariant is enough (all your examples are, and I would think all natural examples ought to be), despite the fact that surely some iso-invariant properties might not seem "natural." A P/NP-hard dichotomy for iso-invariant properties of cubic graphs would be a very interesting theorem. (I say NP-hard and not NPC b/c one can probably cook up an iso-invariant property that is, e.g., PSPACE-complete by considering some game on the graph.)
Joshua Grochow
CC BY-SA 3.0
2014-01-30T03:15:44.783Z
@JoshuaGrochow Thanks for your comment. I hope that the four examples I gave would provide "working" definition of **natural interesting property** of cubic graphs. Personally, I conjecture that deciding any **natural interesting** property of cubic graphs is $NP$-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T12:28:48.513Z
Your edit seems to be restricting to properties that are already in **NP**. Also you don't need to exclude problems that have either a finite number of "yes" instances or a finite number of "no" instances because any such problem is trivially in **P** so could not be a counterexample to your proposed dichotomy.
David Richerby
CC BY-SA 3.0
2014-01-30T17:18:28.643Z
@Mohammad, I removed CW flag, please be more careful with your future edits so it doesn't become CW automatically again.
Kaveh
CC BY-SA 3.0
2014-01-30T18:17:19.737Z
@Kaveh I'll miss you as an excellent moderator. Thanks for your service.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-30T20:20:34.193Z
The restriction to NP problems does nothing to prevent examples such as the GI-complete one in my answer.
David Eppstein
CC BY-SA 3.0
2014-02-01T18:08:45.743Z
this question seems to allude to a "dichotomy thm" analog possibly from somewhere else; are there any examples of other "dichotomy thms" along these lines in the literature?
vzn
CC BY-SA 3.0
2014-02-03T05:02:32.423Z
oh MAT cites [Schaefer dichotomy thm](http://en.wikipedia.org/wiki/Schaefer's_dichotomy_theorem) / wikipedia. so more specifically, are there any other thms that are known to be similar to that one?
vzn
<cc.complexity-theory><graph-theory>
Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?
Mohammad Al-Turkistany
# Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

(Asked by: username_0 on 2014-01-29)

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T\_1 ∪ T\_2$ such that $T\_1$ and $T\_2$ induce trees of equal size (Deciding whether a cubic graph is [Yutsis graph](https://cstheory.stackexchange.com/a/20776/495)). The preceding two example problems demonstrates what I mean by **natural interesting property** of cubic graphs.

Another **natural interesting property** of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which **natural interesting** problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

> Is there a P/NP-complete dichotomy theorem for **natural interesting** properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. [Bach's post](https://cstheory.stackexchange.com/questions/19845/np-complete-graph-problems-about-structural-properties) may help in clarifying my motivation. [My answer](https://cstheory.stackexchange.com/a/19866/495) to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of **connected** cubic graphs.

**EDIT 1-30-2014**: To capture the essence of **natural property** of cubic graphs, I accept a natural $NP$ **property** $X$ of cubic graphs where there is **natural** efficient verifier that verifies a **natural interesting** relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_0**: Although the following does not answer the above question, I am interested in polynomial-time decidable natural interesting properties of cubic graphs. If no such examples exist, It is natural to conjecture that deciding any **natural interesting property** of cubic graphs is $NP$-complete.  
> **username_1**: Interesting question! But in order to get a dichotomy theorem I think one would have to pick a defn of "natural interesting property." Maybe isomorphism-invariant is enough (all your examples are, and I would think all natural examples ought to be), despite the fact that surely some iso-invariant properties might not seem "natural." A P/NP-hard dichotomy for iso-invariant properties of cubic graphs would be a very interesting theorem. (I say NP-hard and not NPC b/c one can probably cook up an iso-invariant property that is, e.g., PSPACE-complete by considering some game on the graph.)  
> **username_0**: @JoshuaGrochow Thanks for your comment. I hope that the four examples I gave would provide "working" definition of **natural interesting property** of cubic graphs. Personally, I conjecture that deciding any **natural interesting** property of cubic graphs is $NP$-complete.  
> **username_2**: Your edit seems to be restricting to properties that are already in **NP**. Also you don't need to exclude problems that have either a finite number of "yes" instances or a finite number of "no" instances because any such problem is trivially in **P** so could not be a counterexample to your proposed dichotomy.  
> **username_3**: @Mohammad, I removed CW flag, please be more careful with your future edits so it doesn't become CW automatically again.  
> **username_0**: @username_3 I'll miss you as an excellent moderator. Thanks for your service.  
> **username_4**: The restriction to NP problems does nothing to prevent examples such as the GI-complete one in my answer.  
> **username_5**: this question seems to allude to a "dichotomy thm" analog possibly from somewhere else; are there any examples of other "dichotomy thms" along these lines in the literature?  
> **username_5**: oh MAT cites [Schaefer dichotomy thm](http://en.wikipedia.org/wiki/Schaefer's_dichotomy_theorem) / wikipedia. so more specifically, are there any other thms that are known to be similar to that one?  

---

## 4 answers

### Answer by username_4 on 2014-01-30. Score: 11 | Accepted answer

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

* Are there evenly many 3-edge-colorings? (Should be $\oplus P$-complete)
* Who wins at strings-and-coins? (Might be PSPACE-complete)
* What is its list coloring or list edge coloring number? (Might be $\Pi^p\_2$-complete)
* Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)
* Given two cubic Halin graphs with the same labeled outer face, how few steps does it take to convert one to the other by alternatingly contracting an interior edge and then uncontracting it the other way? (Equivalent to the open problem of computing rotation distance on binary search trees; might also be interesting for broader classes of cubic graphs)

> **Comments:**
> **username_0**: Thanks for your answer. Are your counter-examples for the class of connected cubic graphs?  
> **username_4**: The whole reason I stated the first example in terms of biconnected components rather than connected components was to make it apply to connected graphs. The other problems decompose on disconnected graphs, so connected graphs are their hardest case.  
> **username_0**: @JoshuaGrochow Isn't GI in P for bounded-degree graphs?  
> **username_1**: Oh, sorry, right. I was being oblivious.  
> **username_4**: Oops, yes, so getting a GI-complete problem out of cubic graphs is not going to be as easy as taking biconnected components. I'll take that one out of the list for now.  
> **username_7**: Can't you just compute the determinant of the adjacency matrix of a graph mod 2 to get the parity of the number of perfect matchings in a graph?  
> **username_4**: Oh, probably. I picked that one over Hamiltonian cycles because there are always an even number of Hamiltonian cycles. But one of those types of problems should be $\oplus\mathsf{P}$-complete; I guess I need to look harder for the right one.  
> **username_4**: I changed it from matchings to 3-edge-colorings for this reason.  

---

### Answer by username_1 on 2014-01-31. Score: 7

Even for problems *within $\mathsf{NP}$*, and even assuming some reasonable notion of "natural property", there is likely no such dichotomy theorem (in addition to the excellent answers of Davids Richerby and Eppstein exhibiting natural problems much harder than $\mathsf{NP}$-complete).

The reason is that there are likely to be natural, interesting properties that are sparse, i.e. only $\leq poly(n)$ many cubic graphs on $n$ vertices have the property (not to be confused with "sparse" in the sense of "sparse graph," which all cubic graphs are). By Mahaney's Theorem, no such problem can be $\mathsf{NP}$-complete. (Assuming $\mathsf{P} \neq \mathsf{NP}$, but that's implicit in the question itself.)

I'd be grateful to anyone who could strengthen this answer by coming up with such a property: natural, interesting, and sparse.


---

### Answer by username_2 on 2014-01-30. Score: 5

There is no **P**-vs-**NP** dichotomy for problems on cubic graphs because there are problems on cubic graphs of arbitrarily high complexity. We can code arbitrary binary strings as cubic graphs, thus translating any question about binary strings into a question about cubic graphs.

For $k\geq 5$, let $W\_k$ be the graph consisting of two disjoint $k$-cycles $x\_1\dots x\_k x\_1$ and $y\_1\dots y\_k y\_1$, along with the matching $x\_2y\_2, \dots, x\_ky\_k$. (Thus, every vertex except $x\_1$ and $x\_2$ has degree 3.) Given an arbitrary binary string $s=s\_1\dots s\_\ell$, let $H\_1 \dots H\_{\ell+4}$ be the following sequence of graphs. For $1\leq i\leq \ell$, let $H\_i = W\_5$ if $s\_i=0$ and $H\_i = W\_7$ if $s\_i=1$. Let $H\_{\ell+1}=H\_{\ell+4}=W\_9$, $H\_{\ell+2} = W\_5$ and $H\_{\ell+3} = W\_7$. Now, let $G\_s$ be the graph made from the sequence of $H$'s by adding an edge between a degree-2 vertex in $H\_i$ and one in $H\_{i+1}$ ($i<\ell+4$) and likewise between $H\_{\ell+4}$ and $H\_1$, thus making a connected, cubic graph. (The purpose of $H\_{\ell+1}, \dots, H\_{\ell+4}$ is just to establish the direction of the cycle.)

Now, take any language $\mathcal{L}\subseteq \{0,1\}^\*$ – it doesn't even have to be decidable. $\mathcal{G} = \{G\_s\mid s\in\mathcal{L}\}$ is a subset of the cubic graphs and determining membership of $\mathcal{G}$ has the same complexity as determining membership of $\mathcal{L}$.

> **Comments:**
> **username_0**: What are you trying to prove with your example? Could you provide a figure to illustrate your idea?  
> **username_0**: I don't see the point. There are undecidable problems in $P/poly$ which contains $P$ ($P/poly$ is considered an acceptable notion of efficiency).  
> **username_2**: You asked if there is a **P**-vs-**NP**-complete dichotomy for problems on cubic graphs. That would mean that *every* problem on cubic graphs would have to be either in **P** or be **NP**-complete (or possibly both at the same time, if **P** = **NP**). I have shown that there are problems on cubic graphs that are not even in **NP**. Such a problem cannot be **NP**-complete or in **P**, which means that your proposed dichotomy does not exist.  
> **username_0**: I don't see a proof that your problem is not in $NP$. Also, as I stated in the problem, I am only interested in $NP$ properties.  
> **username_2**: @MohammadAl-Turkistany "It doesn't even have to be decidable."  

---

### Answer by username_2 on 2014-01-30. Score: 3

No, there is no such theorem. There cannot be such a theorem because a theorem is a formal, proven statement of mathematics and "natural interesting property" is not a formal property and, therefore, nothing can possibly be proven about it.

> **Comments:**
> **username_0**: Thanks for your answer. I am afraid that your answer  implicitly excludes the existence of any reasonable formalization of "natural interesting property" of cubic graphs.  
> **username_6**: I'm guessing @Mohammad was looking for a definition of "natural" in the same vein as Razborov & Rudich's definition in the context of class-separation proofs. I would hazard to guess that doing this in the current context would be much more difficult, as the definition would probably need to be general enough to allow for rather complicated verifiers (so presumably it makes a claim regarding TM/circuit-like structures), yet somehow be restrictive enough to somehow avoid making claims about anything obfuscated (as classifying obfuscated circuits will be hard by definition).  
> **username_2**: @YonatanN Past experience [1](http://cstheory.stackexchange.com/q/20035/17082) [2](http://cs.stackexchange.com/q/19244/9550) indicates that "natural" means "I want to play a game of whack-a-mole where I conjecture something and then try to forbid all the trivial counter-examples that people come up with."  

---

