<p>A (counter)example from the recent research literature: <a href="https://arxiv.org/pdf/1801.03886.pdf" rel="nofollow noreferrer">almost every simply typed <span class="math-container">$\lambda$</span>-calculus term has a long <span class="math-container">$\beta$</span>-reduction sequence</a> (Asada et al., 2019), but this property is very hard to test, even if P = NP!</p>

<p>Asymptotically, almost every STLC term of order <span class="math-container">$k$</span> and length <span class="math-container">$n$</span> has reduction sequence length <span class="math-container">$(2\uparrow \uparrow (k - 1))^{\Theta(n)}$</span>, where <span class="math-container">$2 \uparrow \uparrow n = 2^{2^{2^{...}}}$</span> is the exponential function iterated <span class="math-container">$n$</span> times. However, to test this property, the only way is to <span class="math-container">$\beta$</span>-reduce this term and check the reduction sequence length. STLC is strongly normalizing, so it is certainly decidable, but apparently this will take at least <span class="math-container">$O((2\uparrow \uparrow (k-1))^{\Theta(n)})$</span> time in the worst case, assuming that each reduction step takes <span class="math-container">$O(1)$</span> time. Deciding this property is apparently not in P. In fact, it is in <span class="math-container">$k$</span>-EXPTIME, so it is not in P even if P=NP!</p>

<p>In the other direction, it's trivial to show that the implication doesn't hold: it is easy to check if a STLC term has a polynomial-length reduction sequence, but almost no term has such a short reduction sequence.</p>

CC BY-SA 4.0
2020-01-28T18:11:34.167Z
2020-01-28T18:24:35.953Z
2020-01-28T18:24:35.953Z
xrq
<p>It's quite common for properties split numbers into "almost all" and "almost none" sets. For instance, almost none of Turing machines halt. Almost all real numbers are <a href="https://en.wikipedia.org/wiki/Normal_number" rel="nofollow noreferrer">normal</a>. Almost none of real number are algebraic.</p>

CC BY-SA 4.0
2020-01-21T08:13:26.723Z
This does not seem to answer the OP's question. Can you modify the answer to relate to the property of being testable in polynomial time?
Shaull
CC BY-SA 4.0
2020-01-21T16:58:57.463Z
And how do we know that almost no Turing machines halt? One of the known normal numbers is Chaitin constant - and if almost no Turing machines halt that constant would be almost zero, which isn't normal.
Hans Olsson
CC BY-SA 4.0
2020-01-21T21:12:50.817Z
@HansOlsson: I used a notation for Turing machines for awhile for which most corruptions of interesting Turing machines looped forever.
Joshua
CC BY-SA 4.0
2020-01-21T01:01:51.817Z
2020-01-21T01:01:51.817Z
Acccumulation
<p>They are separate (assuming <span class="math-container">$P \ne NP$</span>).  Consider the following property <span class="math-container">$P(x)$</span>: <span class="math-container">$x$</span> is a <span class="math-container">$2n$</span>-bit string, where either the first <span class="math-container">$n$</span> bits are not all zeros, or the last <span class="math-container">$n$</span> bits are a yes-instance of 3SAT.  It's clear that testing whether <span class="math-container">$x$</span> satisfies <span class="math-container">$P$</span> is NP-hard, yet almost all strings satisfy it: the density <span class="math-container">$\to 1$</span> as <span class="math-container">$n \to \infty$</span>.</p>

CC BY-SA 4.0
2020-01-20T08:12:51.940Z
Nice... anyway you don't need to assume P!=NP, just replace 3SAT by any problem known to not be in P, say an EXPTIME-complete problem
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2020-01-20T12:11:36.930Z
This proves one direction. The implication in other direction is intuitively wrong; So, this answer completes the picture.
Cyriac Antony
CC BY-SA 4.0
2020-01-20T17:56:20.977Z
@CyriacAntony For an explicit counterexample to the other direction, consider the set of strings of even length - easy to recognize, but neither it nor its complement is "almost everything." *(And this can be easily tweaked to a set of strings whose limsup frequency is 1 and whose liminf frequency is 0.)*
Noah Schweber
CC BY-SA 4.0
2020-01-20T07:03:24.303Z
2020-01-20T08:45:19.033Z
2020-01-20T08:45:19.033Z
D.W.
<p>I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".</p>

<p>My guess is that they are completely separate (that is, one doesn't imply the other). Am I missing something?</p>

<p>(Note: <em>Almost all</em> in the sense of probability)</p>

<p>PS: I am not sure whether the tag probability is appropriate here, sorry.</p>

CC BY-SA 4.0
2020-01-20T21:50:58.707Z
Almost all reals are irrational. But testing whether "$0$ if Golbach's Conjecture is true and $\sqrt 2$ if it is not" is irrational is not easy
Hagen von Eitzen
CC BY-SA 4.0
2020-01-21T00:34:21.227Z
@HagenvonEitzen How is that a property?
Acccumulation
CC BY-SA 4.0
2020-01-21T04:32:20.350Z
Almost all strings are not valid C programs that loop forever. But it's very, very hard to test this property.
Daniel Wagner
CC BY-SA 4.0
2020-01-21T13:12:31.340Z
@Acccumulation being rational is a property. H von E wants to test this property on a number that has a somewhat annoying definition and finds that it is hard. So one thing we can conclude that how hard it is to test a property of a given object depends at least in part on how the object is presented to you
Vincent
CC BY-SA 4.0
2020-01-21T16:10:46.687Z
@DanielWagner Isn't that halting problem?
Cyriac Antony
CC BY-SA 4.0
2020-01-21T16:39:59.007Z
@CyriacAntony It is indeed! As problems go, there are few practically interesting ones that are harder.
Daniel Wagner
CC BY-SA 4.0
2020-01-21T16:40:38.273Z
@DanielWagner Don't forget tiling!
Cyriac Antony
<cc.complexity-theory><pr.probability>
"Almost all objects have property P" vs. "It is easy to test whether an object has property P"
Cyriac Antony
# "Almost all objects have property P" vs. "It is easy to test whether an object has property P"

(Asked by: username_0 on 2020-01-20)

I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".

My guess is that they are completely separate (that is, one doesn't imply the other). Am I missing something?

(Note: *Almost all* in the sense of probability)

PS: I am not sure whether the tag probability is appropriate here, sorry.

**Tags:** cc.complexity-theory, pr.probability
> **Comments:**
> **username_1**: Almost all reals are irrational. But testing whether "$0$ if Golbach's Conjecture is true and $\sqrt 2$ if it is not" is irrational is not easy  
> **username_2**: @HagenvonEitzen How is that a property?  
> **username_3**: Almost all strings are not valid C programs that loop forever. But it's very, very hard to test this property.  
> **username_4**: @Acccumulation being rational is a property. H von E wants to test this property on a number that has a somewhat annoying definition and finds that it is hard. So one thing we can conclude that how hard it is to test a property of a given object depends at least in part on how the object is presented to you  
> **username_0**: @DanielWagner Isn't that halting problem?  
> **username_3**: @CyriacAntony It is indeed! As problems go, there are few practically interesting ones that are harder.  
> **username_0**: @DanielWagner Don't forget tiling!  

---

## 3 answers

### Answer by username_9 on 2020-01-20. Score: 25 | Accepted answer

They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance of 3SAT. It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.

> **Comments:**
> **username_10**: Nice... anyway you don't need to assume P!=NP, just replace 3SAT by any problem known to not be in P, say an EXPTIME-complete problem  
> **username_0**: This proves one direction. The implication in other direction is intuitively wrong; So, this answer completes the picture.  
> **username_11**: @CyriacAntony For an explicit counterexample to the other direction, consider the set of strings of even length - easy to recognize, but neither it nor its complement is "almost everything." *(And this can be easily tweaked to a set of strings whose limsup frequency is 1 and whose liminf frequency is 0.)*  

---

### Answer by username_5 on 2020-01-28. Score: 2

A (counter)example from the recent research literature: [almost every simply typed $\lambda$-calculus term has a long $\beta$-reduction sequence](https://arxiv.org/pdf/1801.03886.pdf) (Asada et al., 2019), but this property is very hard to test, even if P = NP!

Asymptotically, almost every STLC term of order $k$ and length $n$ has reduction sequence length $(2\uparrow \uparrow (k - 1))^{\Theta(n)}$, where $2 \uparrow \uparrow n = 2^{2^{2^{...}}}$ is the exponential function iterated $n$ times. However, to test this property, the only way is to $\beta$-reduce this term and check the reduction sequence length. STLC is strongly normalizing, so it is certainly decidable, but apparently this will take at least $O((2\uparrow \uparrow (k-1))^{\Theta(n)})$ time in the worst case, assuming that each reduction step takes $O(1)$ time. Deciding this property is apparently not in P. In fact, it is in $k$-EXPTIME, so it is not in P even if P=NP!

In the other direction, it's trivial to show that the implication doesn't hold: it is easy to check if a STLC term has a polynomial-length reduction sequence, but almost no term has such a short reduction sequence.


---

### Answer by username_2 on 2020-01-21. Score: 0

It's quite common for properties split numbers into "almost all" and "almost none" sets. For instance, almost none of Turing machines halt. Almost all real numbers are [normal](https://en.wikipedia.org/wiki/Normal_number). Almost none of real number are algebraic.

> **Comments:**
> **username_6**: This does not seem to answer the OP's question. Can you modify the answer to relate to the property of being testable in polynomial time?  
> **username_7**: And how do we know that almost no Turing machines halt? One of the known normal numbers is Chaitin constant - and if almost no Turing machines halt that constant would be almost zero, which isn't normal.  
> **username_8**: @HansOlsson: I used a notation for Turing machines for awhile for which most corruptions of interesting Turing machines looped forever.  

---

