13
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – Hagen von Eitzen
    Commented Jan 20, 2020 at 21:50
  • $\begingroup$ @HagenvonEitzen How is that a property? $\endgroup$
    – Acccumulation
    Commented Jan 21, 2020 at 0:34
  • 7
    $\begingroup$ Almost all strings are not valid C programs that loop forever. But it's very, very hard to test this property. $\endgroup$
    – Daniel Wagner
    Commented Jan 21, 2020 at 4:32
  • $\begingroup$ @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 $\endgroup$
    – Vincent
    Commented Jan 21, 2020 at 13:12
  • $\begingroup$ @DanielWagner Isn't that halting problem? $\endgroup$
    – Cyriac Antony
    Commented Jan 21, 2020 at 16:10

3 Answers 3

Reset to default
25
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • 13
    $\begingroup$ 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 $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 20, 2020 at 8:12
  • $\begingroup$ This proves one direction. The implication in other direction is intuitively wrong; So, this answer completes the picture. $\endgroup$
    – Cyriac Antony
    Commented Jan 20, 2020 at 12:11
  • 3
    $\begingroup$ @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.) $\endgroup$
    – Noah Schweber
    Commented Jan 20, 2020 at 17:56
2
$\begingroup$

A (counter)example from the recent research literature: almost every simply typed $\lambda$-calculus term has a long $\beta$-reduction sequence (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.

Improve this answer
$\endgroup$
0
$\begingroup$

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. Almost none of real number are algebraic.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Commented Jan 21, 2020 at 8:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hans Olsson
    Commented Jan 21, 2020 at 16:58
  • $\begingroup$ @HansOlsson: I used a notation for Turing machines for awhile for which most corruptions of interesting Turing machines looped forever. $\endgroup$
    – Joshua
    Commented Jan 21, 2020 at 21:12

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.