Content deleted Content added
→Cryptography: Factoring integers is not known to be NP hard. |
m link non-deterministic Turing machine using Find link |
||
Line 61:
An example of a distNP-complete problem is the Bounded Halting Problem, BH, defined as follows:
BH = {(M,x,1<sup>t</sup>) : M is a [[non-deterministic Turing machine]] that accepts x in ≤ t steps.}<ref name="ab09"/>
In his original paper, Levin showed an example of a distributional tiling problem that is average-case NP-complete.<ref name="levin86"/> A survey of known distNP-complete problems is available online.<ref name="wangsurvey"/>
| |||