While there is no known counterexample to the assumption that the probabilistic
[Baillie–PSW primality test][1] is actually a proper primality test, there is strong
evidence that there exist such counterexamples. -- In 1984, [Carl Pomerance][2] has
even given a heuristic argument (see [here][3]) that for any $\epsilon > 0$ and large
enough $x$, the number of composites $\leq x$ failing the test is larger than
$x^{1-\epsilon}$ -- yet none is known so far.

  [1]: http://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
  [2]: http://en.wikipedia.org/wiki/Carl_Pomerance
  [3]: http://www.pseudoprime.com/dopo.pdf